# Maximize the minimum difference between any element pair by selecting K elements from given Array

Given an array of** N** integers the task is to select** K** elements out of these **N** elements in such a way that the minimum difference between each of the K numbers is the Largest. Return** **the largest minimum difference after choosing any **K** elements.

**Examples:**

Input:N = 4, K = 3, arr = [2, 6, 2, 5]Output:1Explanation:3 elements out of 4 elements are to be selected with a minimum difference as large as possible. Selecting 2, 2, 5 will result in minimum difference as 0. Selecting 2, 5, 6 will result in minimum difference as 6-5=1

Input:N = 7, K = 4, arr = [1, 4, 9, 0, 2, 13, 3]Output:4Explanation:Selecting 0, 4, 9, 13 will result in minimum difference of 4, which is the largest minimum difference possible

**Naive Approach: **Generate all the subsets of size K and find the minimum difference in all of them. Then return the maximum among the differences.

**Efficient Approach: **Given problem can be solved efficiently using binary search on answer technique. Below steps can be followed to solve the problem:

- Sort the array in ascending order
- Initialize minimum answer
**ans**to 1 - Binary search is used on the range 1 to maximum element in array
**arr** - Variable
**dif**is used to store the largest minimum difference at every iteration - Helper function is used to check if selection of
**K**elements is possible with minimum difference greater than**dif**calculated in previous iteration. If possible then true is returned or else false is returned. - If above function returns:
- True then update
**ans**to**dif**and left to**dif**+ 1 - False then update right to
**dif**– 1

- True then update

Below is the implementation of the above binary search approach

## C++

`// C++ implementation for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// To check if selection of K elements` `// is possible such that difference` `// between them is greater than dif` `bool` `isPossibleToSelect(` `int` `arr[], ` `int` `N,` ` ` `int` `dif, ` `int` `K)` `{` ` ` `// Selecting first element in the` ` ` `// sorted array` ` ` `int` `count = 1;` ` ` `// prev is the previously selected` ` ` `// element initially at index 0 as` ` ` `// first element is already selected` ` ` `int` `prev = arr[0];` ` ` `// Check if selection of K-1 elements` ` ` `// from array with a minimum` ` ` `// difference of dif is possible` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `// If the current element is` ` ` `// atleast dif difference apart` ` ` `// from the previously selected` ` ` `// element then select the current` ` ` `// element and increase the count` ` ` `if` `(arr[i] >= (prev + dif)) {` ` ` `count++;` ` ` `// If selection of K elements` ` ` `// with a min difference of dif` ` ` `// is possible then return true` ` ` `if` `(count == K)` ` ` `return` `true` `;` ` ` `// Prev will become current` ` ` `// element for the next iteration` ` ` `prev = arr[i];` ` ` `}` ` ` `}` ` ` `// If selection of K elements with minimum` ` ` `// difference of dif is not possible` ` ` `// then return false` ` ` `return` `false` `;` `}` `int` `binarySearch(` `int` `arr[], ` `int` `left,` ` ` `int` `right, ` `int` `K, ` `int` `N)` `{` ` ` `// Minimum largest difference` ` ` `// possible is 1` ` ` `int` `ans = 1;` ` ` `while` `(left <= right) {` ` ` `int` `dif = left + (right - left) / 2;` ` ` `// Check if selection of K elements` ` ` `// is possible with a minimum` ` ` `// difference of dif` ` ` `if` `(isPossibleToSelect(arr, N,` ` ` `dif, K)) {` ` ` `// If dif is greater than` ` ` `// previous ans we update ans` ` ` `ans = max(ans, dif);` ` ` `// Continue to search for better` ` ` `// answer. Try finding greater dif` ` ` `left = dif + 1;` ` ` `}` ` ` `// K elements cannot be selected` ` ` `else` ` ` `right = dif - 1;` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `N, K;` ` ` `N = 7, K = 4;` ` ` `int` `arr[] = { 1, 4, 9, 0, 2, 13, 3 };` ` ` `// arr should be in a sorted order` ` ` `sort(arr, arr + N);` ` ` `cout << binarySearch(arr, 0, arr[N - 1], K, N)` ` ` `<< ` `"\n"` `;` ` ` `return` `0;` `}` |

## Java

`// Java implementation for the above approach` `import` `java.io.*;` `import` `java.util.Arrays;` `class` `GFG{` ` ` `// To check if selection of K elements` ` ` `// is possible such that difference` ` ` `// between them is greater than dif` ` ` `static` `boolean` `isPossibleToSelect(` `int` `[]arr, ` `int` `N,` ` ` `int` `dif, ` `int` `K)` ` ` `{` ` ` `// Selecting first element in the` ` ` `// sorted array` ` ` `int` `count = ` `1` `;` ` ` `// prev is the previously selected` ` ` `// element initially at index 0 as` ` ` `// first element is already selected` ` ` `int` `prev = arr[` `0` `];` ` ` `// Check if selection of K-1 elements` ` ` `// from array with a minimum` ` ` `// difference of dif is possible` ` ` `for` `(` `int` `i = ` `1` `; i < N; i++) {` ` ` `// If the current element is` ` ` `// atleast dif difference apart` ` ` `// from the previously selected` ` ` `// element then select the current` ` ` `// element and increase the count` ` ` `if` `(arr[i] >= (prev + dif)) {` ` ` `count++;` ` ` `// If selection of K elements` ` ` `// with a min difference of dif` ` ` `// is possible then return true` ` ` `if` `(count == K)` ` ` `return` `true` `;` ` ` `// Prev will become current` ` ` `// element for the next iteration` ` ` `prev = arr[i];` ` ` `}` ` ` `}` ` ` `// If selection of K elements with minimum` ` ` `// difference of dif is not possible` ` ` `// then return false` ` ` `return` `false` `;` ` ` `}` ` ` `static` `int` `binarySearch(` `int` `[]arr, ` `int` `left,` ` ` `int` `right, ` `int` `K, ` `int` `N)` ` ` `{` ` ` `// Minimum largest difference` ` ` `// possible is 1` ` ` `int` `ans = ` `1` `;` ` ` `while` `(left <= right) {` ` ` `int` `dif = left + (right - left) / ` `2` `;` ` ` `// Check if selection of K elements` ` ` `// is possible with a minimum` ` ` `// difference of dif` ` ` `if` `(isPossibleToSelect(arr, N,` ` ` `dif, K)) {` ` ` `// If dif is greater than` ` ` `// previous ans we update ans` ` ` `ans = Math.max(ans, dif);` ` ` `// Continue to search for better` ` ` `// answer. Try finding greater dif` ` ` `left = dif + ` `1` `;` ` ` `}` ` ` `// K elements cannot be selected` ` ` `else` ` ` `right = dif - ` `1` `;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `N, K;` ` ` `N = ` `7` `;` ` ` `K = ` `4` `;` ` ` `int` `[]arr = { ` `1` `, ` `4` `, ` `9` `, ` `0` `, ` `2` `, ` `13` `, ` `3` `};` ` ` `// arr should be in a sorted order` ` ` `Arrays.sort(arr);` ` ` `System.out.println(binarySearch(arr, ` `0` `, arr[N - ` `1` `], K, N));` ` ` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Python3

`# Python 3 implementation for the above approach` `# To check if selection of K elements` `# is possible such that difference` `# between them is greater than dif` `def` `isPossibleToSelect(arr, N,` ` ` `dif, K):` ` ` `# Selecting first element in the` ` ` `# sorted array` ` ` `count ` `=` `1` ` ` `# prev is the previously selected` ` ` `# element initially at index 0 as` ` ` `# first element is already selected` ` ` `prev ` `=` `arr[` `0` `]` ` ` `# Check if selection of K-1 elements` ` ` `# from array with a minimum` ` ` `# difference of dif is possible` ` ` `for` `i ` `in` `range` `(` `1` `, N):` ` ` `# If the current element is` ` ` `# atleast dif difference apart` ` ` `# from the previously selected` ` ` `# element then select the current` ` ` `# element and increase the count` ` ` `if` `(arr[i] >` `=` `(prev ` `+` `dif)):` ` ` `count ` `+` `=` `1` ` ` `# If selection of K elements` ` ` `# with a min difference of dif` ` ` `# is possible then return true` ` ` `if` `(count ` `=` `=` `K):` ` ` `return` `True` ` ` `# Prev will become current` ` ` `# element for the next iteration` ` ` `prev ` `=` `arr[i]` ` ` `# If selection of K elements with minimum` ` ` `# difference of dif is not possible` ` ` `# then return false` ` ` `return` `False` `def` `binarySearch(arr, left,` ` ` `right, K, N):` ` ` `# Minimum largest difference` ` ` `# possible is 1` ` ` `ans ` `=` `1` ` ` `while` `(left <` `=` `right):` ` ` `dif ` `=` `left ` `+` `(right ` `-` `left) ` `/` `/` `2` ` ` `# Check if selection of K elements` ` ` `# is possible with a minimum` ` ` `# difference of dif` ` ` `if` `(isPossibleToSelect(arr, N, dif, K)):` ` ` `# If dif is greater than` ` ` `# previous ans we update ans` ` ` `ans ` `=` `max` `(ans, dif)` ` ` `# Continue to search for better` ` ` `# answer. Try finding greater dif` ` ` `left ` `=` `dif ` `+` `1` ` ` `# K elements cannot be selected` ` ` `else` `:` ` ` `right ` `=` `dif ` `-` `1` ` ` `return` `ans` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `7` ` ` `K ` `=` `4` ` ` `arr ` `=` `[` `1` `, ` `4` `, ` `9` `, ` `0` `, ` `2` `, ` `13` `, ` `3` `]` ` ` `# arr should be in a sorted order` ` ` `arr.sort()` ` ` `print` `(binarySearch(arr, ` `0` `, arr[N ` `-` `1` `], K, N)` ` ` `)` ` ` `# This code is contributed by ukasp.` |

## C#

`// C# implementation for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// To check if selection of K elements` `// is possible such that difference` `// between them is greater than dif` `static` `bool` `isPossibleToSelect(` `int` `[]arr, ` `int` `N,` ` ` `int` `dif, ` `int` `K)` `{` ` ` `// Selecting first element in the` ` ` `// sorted array` ` ` `int` `count = 1;` ` ` `// prev is the previously selected` ` ` `// element initially at index 0 as` ` ` `// first element is already selected` ` ` `int` `prev = arr[0];` ` ` `// Check if selection of K-1 elements` ` ` `// from array with a minimum` ` ` `// difference of dif is possible` ` ` `for` `(` `int` `i = 1; i < N; i++) {` ` ` `// If the current element is` ` ` `// atleast dif difference apart` ` ` `// from the previously selected` ` ` `// element then select the current` ` ` `// element and increase the count` ` ` `if` `(arr[i] >= (prev + dif)) {` ` ` `count++;` ` ` `// If selection of K elements` ` ` `// with a min difference of dif` ` ` `// is possible then return true` ` ` `if` `(count == K)` ` ` `return` `true` `;` ` ` `// Prev will become current` ` ` `// element for the next iteration` ` ` `prev = arr[i];` ` ` `}` ` ` `}` ` ` `// If selection of K elements with minimum` ` ` `// difference of dif is not possible` ` ` `// then return false` ` ` `return` `false` `;` `}` `static` `int` `binarySearch(` `int` `[]arr, ` `int` `left,` ` ` `int` `right, ` `int` `K, ` `int` `N)` `{` ` ` `// Minimum largest difference` ` ` `// possible is 1` ` ` `int` `ans = 1;` ` ` `while` `(left <= right) {` ` ` `int` `dif = left + (right - left) / 2;` ` ` `// Check if selection of K elements` ` ` `// is possible with a minimum` ` ` `// difference of dif` ` ` `if` `(isPossibleToSelect(arr, N,` ` ` `dif, K)) {` ` ` `// If dif is greater than` ` ` `// previous ans we update ans` ` ` `ans = Math.Max(ans, dif);` ` ` `// Continue to search for better` ` ` `// answer. Try finding greater dif` ` ` `left = dif + 1;` ` ` `}` ` ` `// K elements cannot be selected` ` ` `else` ` ` `right = dif - 1;` ` ` `}` ` ` `return` `ans;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `N, K;` ` ` `N = 7;` ` ` `K = 4;` ` ` `int` `[]arr = { 1, 4, 9, 0, 2, 13, 3 };` ` ` `// arr should be in a sorted order` ` ` `Array.Sort(arr);` ` ` `Console.Write(binarySearch(arr, 0, arr[N - 1], K, N));` `}` `}` `// This code is contributed by SURENDRA_GANGWAR.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// To check if selection of K elements` ` ` `// is possible such that difference` ` ` `// between them is greater than dif` ` ` `function` `isPossibleToSelect(arr, N,` ` ` `dif, K)` ` ` `{` ` ` ` ` `// Selecting first element in the` ` ` `// sorted array` ` ` `let count = 1;` ` ` `// prev is the previously selected` ` ` `// element initially at index 0 as` ` ` `// first element is already selected` ` ` `let prev = arr[0];` ` ` `// Check if selection of K-1 elements` ` ` `// from array with a minimum` ` ` `// difference of dif is possible` ` ` `for` `(let i = 1; i < N; i++) {` ` ` `// If the current element is` ` ` `// atleast dif difference apart` ` ` `// from the previously selected` ` ` `// element then select the current` ` ` `// element and increase the count` ` ` `if` `(arr[i] >= (prev + dif)) {` ` ` `count++;` ` ` `// If selection of K elements` ` ` `// with a min difference of dif` ` ` `// is possible then return true` ` ` `if` `(count == K)` ` ` `return` `true` `;` ` ` `// Prev will become current` ` ` `// element for the next iteration` ` ` `prev = arr[i];` ` ` `}` ` ` `}` ` ` `// If selection of K elements with minimum` ` ` `// difference of dif is not possible` ` ` `// then return false` ` ` `return` `false` `;` ` ` `}` ` ` `function` `binarySearch(arr, left,` ` ` `right, K, N) {` ` ` `// Minimum largest difference` ` ` `// possible is 1` ` ` `let ans = 1;` ` ` `while` `(left <= right) {` ` ` `let dif = left + Math.floor((right - left) / 2);` ` ` `// Check if selection of K elements` ` ` `// is possible with a minimum` ` ` `// difference of dif` ` ` `if` `(isPossibleToSelect(arr, N,` ` ` `dif, K)) {` ` ` `// If dif is greater than` ` ` `// previous ans we update ans` ` ` `ans = Math.max(ans, dif);` ` ` `// Continue to search for better` ` ` `// answer. Try finding greater dif` ` ` `left = dif + 1;` ` ` `}` ` ` `// K elements cannot be selected` ` ` `else` ` ` `right = dif - 1;` ` ` `}` ` ` `return` `ans;` ` ` `}` ` ` `// Driver code` ` ` `let N, K;` ` ` `N = 7, K = 4;` ` ` `let arr = [1, 4, 9, 0, 2, 13, 3];` ` ` `// arr should be in a sorted order` ` ` `arr.sort(` `function` `(a, b) { ` `return` `a - b })` ` ` `document.write(binarySearch(arr, 0, arr[N - 1], K, N)` ` ` `+ ` `'<br>'` `);` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

4

**Time complexity: **O(N * log N) **Space complexity: **O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.