Minimum Difference Between Highest and Lowest of K Scores
You are given an array numsk
Example 1
Output: 0
Example 2
Output: 2
Explanation: pick 9 and 7.
How to Think About It
Step 1: Trying every group is far too slow
There are "n choose k" groups of k scores, which explodes quickly.
Step 2: Sort, and the best group is a run of neighbours
After sorting, suppose a best group has lowest score nums[i]nums[i + k - 1]nums[i]nums[i..i+k-1]
Step 3: Slide a window of size k
For each start i, the window's difference is nums[i + k - 1] - nums[i]
Walkthrough
nums = [9, 4, 1, 7]k = 2[1, 4, 7, 9]
| Window | Highest - lowest |
|---|---|
| [1, 4] | 3 |
| [4, 7] | 3 |
| [7, 9] | 2 |
Java Solution
With k = 1 every window has one value and the difference is 0, so no special case is needed.
import java.util.Arrays;
public class MinimumDiffBetweenHighestAndLowestOfKScores {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int best = Integer.MAX_VALUE;
for (int i = 0; i + k - 1 < nums.length; i++) {
best = Math.min(best, nums[i + k - 1] - nums[i]); // k neighbours in sorted order
}
return best;
}
}
The original implementation,
Complexity
- Time: O(n log n) for the sort.
- Space: O(1) besides the sort.
Sorting so that the best choice becomes a contiguous run also solves