Two Pointers: Given an array and a value “m”, choose “m” elements having minimum difference between max and min

Problem Statement:

You are given an array and a value “m”.

You need to pick exactly m elements such that the difference between the maximum number and minimum number is minimum.

Example:

Input: arr[] = {7, 3, 2, 4, 9, 12, 56}, m = 3 
Output: 2

Pick the sub array {3, 2, 4}.

Here the max value is 4 and min value is 2.

4 - 2 = 2. Hence the result.

Solution Explanation:

We can use the sliding window approach to solve this problem.

We will choose consecutive elements from a sorted array to minimize the difference.

Time Complexity: n*log(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int getMinDiff(vector<int> &arr, int m) {

	int n = arr.size();

    sort(arr.begin(), arr.end());

    int minDiff = INT_MAX;

    for (int i = 0; i + m - 1 < n; i++) {
      	
      	// calculate difference of current window
        int diff = arr[i + m - 1] - arr[i];
      
        if (diff < minDiff)
        	minDiff = diff;
    }
    return minDiff;
}

int main() {
    
    vector<int> arr = {7, 3, 2, 4, 9, 12, 56};
    int m = 3;
  	
    cout << getMinDiff(arr, m);
    return 0;
}

Output

2