visual walkthrough
Minimum Difference Between Highest and Lowest of K Scores
Sorting makes the best window contiguous.
The idea
To make the highest and lowest as close as possible, the k scores should be a tight cluster. In sorted order, a tight cluster is just k consecutive scores.
So after sorting, slide a window of size k and take the smallest (last − first).
Complexity
| approach | time | space |
|---|---|---|
| Try every group | O(C(n, k) · k) | O(k) |
| Sort + fixed window | O(n log n) | O(1) |