Minimum difference between max and min of all K-size subsets - GeeksforGeeks

Minimum difference between max and min of all K-size subsets - GeeksforGeeks
Given an array of integer values, we need to find the minimum difference between maximum and minimum of all possible K-length subsets.

We can solve this problem without iterating over all possible subsets by observing the fact that our result subset will always be consecutive, once we sort the given array. The reason is sorting brings value-wise close elements together.
We can prove above fact as follows – Suppose we chose number a1, a2, a3 … aK which are in increasing order but not continuous, then our difference will be (aK – a1) but if we include the number which was not taken earlier (let aR) then our K length subset will be a2, a3, … aR, …. aK. In this case, our difference will (aK – a2) which must be smaller than (aK – a1) because a2 > a1. So we can say that the subset which will contain our answer will always be consecutive in sorted array.
Stating above fact, for solving the problem first we sort the array then we will iterate over first (N – K) elements and each time we will take the difference between elements which are K distant apart and our final answer will be minimum of them.

int minDifferenceAmongMaxMin(int arr[], int N, int K)

{

    // sort the array so that close

    // elements come together.

    sort(arr, arr + N);

 

    //  initialize result by a big integer number

    int res = INT_MAX;

 

    // loop over first (N - K) elements

    // of the array only

    for (int i = 0; i <= (N - K); i++)

    {

        //  get difference between max and min of

        // current K-sized segment

        int curSeqDiff = arr[i + K - 1] - arr[i];

        res = min(res, curSeqDiff);

    }

 

    return res;

}

Read full article from Minimum difference between max and min of all K-size subsets - GeeksforGeeks