Max Min | HackerRank Solution [Medium]

Problem

You will be given a list of integers, arr[], and a single integer k. You must create an array of length k from elements of arr[] such that its unfairness is minimized. Call that array arr'. Unfairness of an array is calculated as:

max(arr’) – min(arr’)

Where:
– max denotes the largest integer in arr'
– min denotes the smallest integer in arr'

HackerRank Problem Link

Input

The first line contains an integer n, the number of elements in array arr.
The second line contains an integer k.
Each of the next n lines contains an integer arr[i] where 0 <= i < n

Output

int: the minimum possible unfairness

Constraints

• 2 <= n ≤ 10⁵
• 2 <= k <= n
• 0 <= arr[i] <= 10⁹

Sample Input

7
3
10
100
300
200
1000
20
30

Sample Output

20

Explanation
Here k = 3; selecting the integers 10, 20, 30, unfairness equals 20:
max(10, 20, 30) - min(10, 20, 30) = 30 - 10 = 20

Solution

Approach: Greedy Algorithm and Sorting

Code Implementation

//
//  main.cpp
//  Max Min
//
//  Created by Himanshu on 22/03/22.
//
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
    int n, k, unfairness = INT_MAX;;
    cin>>n>>k;
    
    int *candies = new int[n];
    
    for (int i=0; i<n; i++) {
        cin>>candies[i];
    }
    
    // Minimum difference between max[element] and min[element] would happen
    // when they are near to each other in counting
    sort(candies,candies+n);
    
    for (int i=0; (i+k)<=n; i++) {
        unfairness = min(unfairness, (candies[i+k-1]-candies[i]));
    }
    
    cout<<unfairness<<endl;
    return 0;
}

Time complexity: O(n*logn)