Max min Solution

This is one of the medium difficulty problems in the Greedy algorithms section of Hackerrank’s interview preparation kit problem set. Link here.

The problem states that given an array of integers arr and an integer k . You need to produce a subarray of arr of length k such that

MAX(subarray)-MIN(subarray)is minimized.

Solution

To solve this problem there is no need to generate all subarrays. That would be the brute force solution and we can do much better than that. What we do instead is we sort in decreasing order and look for the pairs that minimize the difference.

Since we have the array sorted the min and max of any subarray of length k will be the first and last element . We look for all such pairs in the array and return the minimum difference.

Code

Link to Github solution

static bool sortFn(int a, int b){return a < b;}
static int diff = INT_MAX;
int maxMin(int k, vector<int> arr) {
    sort(arr.begin(), arr.end(), sortFn);
    
    for(int i = 0; i <= arr.size()-k; i++)
        diff = min(arr[i+k-1]-arr[i], diff);
    
    return diff;
}