# 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'

#### 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 ≤ 105
• 2 <= k <= n
• 0 <= arr[i] <= 109

#### 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

//
//  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)