Minimum Difference Between Highest and Lowest of K Scores

Minimum Difference Between Highest and Lowest of K Scores

1. What is this problem about?

The Minimum Difference Between Highest and Lowest of K Scores problem asks you to select exactly $K$ scores from an array of $N$ scores such that the difference between the highest and the lowest score in your selection is minimized. This is a classic optimization problem that involves picking a subset of elements that are as "close" to each other as possible.

2. Why is this asked in interviews?

Companies like Meta and Amazon ask this "Easy" question to test a candidate's understanding of sorting and the sliding window technique. The Minimum Difference Between Highest and Lowest of K Scores interview question evaluates if you can recognize that the most "compact" group of $K$ elements will always be contiguous once the array is sorted. It's a foundational problem for more complex optimization challenges.

3. Algorithmic pattern used

The primary algorithmic pattern is Sorting and Sliding Window.

1. Sort the array of scores in non-decreasing order.
2. Once sorted, any $K$ contiguous elements represent a possible selection. The difference between the highest and lowest in such a selection is $nums[i+K-1] - nums[i]$.
3. Use a sliding window of size $K$ to iterate through the sorted array.
4. Keep track of the minimum difference found. This "Array, Sorting, Sliding Window interview pattern" runs in $O(N \log N)$ time due to sorting and $O(1)$ extra space.

4. Example explanation

Scores: [9, 4, 1, 7], $K = 2$.

1. Sort scores: [1, 4, 7, 9].
2. Window 1 (indices 0 to 1): [1, 4]. Difference = $4-1 = 3$.
3. Window 2 (indices 1 to 2): [4, 7]. Difference = $7-4 = 3$.
4. Window 3 (indices 2 to 3): [7, 9]. Difference = $9-7 = 2$. Minimum difference is 2.

5. Common mistakes candidates make

In the Minimum Difference Between Highest and Lowest of K Scores coding problem, the most common mistake is trying to use a combinations-based approach, which is $O(N^K)$ and extremely inefficient. Another mistake is forgetting to sort the array; without sorting, there is no easy way to identify the $K$ elements that are closest to each other. Some candidates also mess up the sliding window boundaries, either starting too late or ending too early.

6. Interview preparation tip

Whenever you need to find a subset of elements that minimizes a range-based property (like max - min), sorting is almost always the first step. Once sorted, the elements you are looking for will be adjacent. This "Sorting-based optimization interview pattern" is a very powerful mental model for solving array problems.