Max Min HackerRank Problem
Task:- Given an array of integers and value ‘k’. Calculate the minimum unfairness value possible with an array of ‘k’ elements from the given array.
Unfairness = max(arr) — min(arr)
For eg: arr = [ 2, 8, 2, 4, 4, 1 ] and k = 4
The array [ 2, 4, 2, 4 ] gives the minimum unfairness value possible which is 4–2 = 2.
Note that we can rearrange the numbers.
Approach:- We can sort the array in the ascending order and check the minimum possible value of difference between elements with distance ‘k’ apart. This makes sure that for a given length ‘k’ we will get the maximum and minimum element of a subarray at index ‘i+k-1’ and index ‘i’ respectively.
The time complexity of this approach will be O(N.logN) which is for sorting the array. We also traverse the array linearly but the overall time complexity remains O(N.logN).
Code:-
