Problem Statement:
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 subarr.
Unfairness of an array is calculated as: max(subarr) - min(subarr)
Where:
- max denotes the largest integer in subarr
- min denotes the smallest integer in subarr
Complete the maxMin function in the editor below. It must return an integer that denotes the minimum possible value of unfairness.
Solution:
static int maxMin(int k, int[] arr) {
int arrLen = arr.length;
Arrays.sort(arr);
int[] subArr = Arrays.copyOfRange(arr, 0, k);
int minUnfairness = subArr[k - 1] - subArr[0];
for ( int j = 1; j < arrLen - k + 1; j++ ) {
subArr = Arrays.copyOfRange(arr, j, j+k);
int tempMinUnfairness = subArr[ k - 1 ] - subArr[0];
if ( tempMinUnfairness < minUnfairness ) {
minUnfairness = tempMinUnfairness;
}
}
return minUnfairness;
}
/**
* Valid Test Case For Reference
*/
private static void validTest() {
int[] arr = { 10,100,300,200,1000,20,30 };
int expected = 20;
int result = maxMin(3, arr);
assert (result == expected);
}
The main function to review is maxMin().
Looking forward to your reviews on -
- What other improvements can be done?
- What other ways could be there to the problem, as the current approach is Greedy?
Thank you.