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

0 0 9 minutes read

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: 1
Explanation: 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: 4
Explanation: 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

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

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!