# 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
731010030020010002030
###### Sample Output
20ExplanationHere 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)