Minimum Difference Between Highest and Lowest of K Scores - Video Solutions

Problem Overview: You receive an array of student scores and an integer k. Choose any k scores such that the difference between the highest and lowest score in that group is as small as possible. Return that minimum difference.

The key observation: once the scores are ordered, the best group of k scores must appear as a contiguous segment in the sorted list. Any non‑contiguous choice would only increase the difference between the minimum and maximum values.

Approach 1: Sorting and Sliding Window (Time: O(n log n), Space: O(1) or O(n) depending on sort)

Start by sorting the scores using a standard sorting algorithm. After sorting, every valid group of k elements appears as a contiguous window. Slide a window of size k from left to right and compute nums[i + k - 1] - nums[i] for each position. Track the minimum difference across all windows.

This works because sorting ensures the smallest value in the window is at the left boundary and the largest at the right boundary. The algorithm performs a single pass after sorting, making the window scan O(n). The technique resembles a classic sliding window over a sorted array. This is the standard and most efficient approach used in interviews.

Approach 2: Dynamic Programming Style Buckets (Time: O(n + R), Space: O(R))

If score values fall within a limited range, you can avoid sorting by using buckets. Create a frequency array where the index represents a score and the value represents how many students have that score. Then simulate collecting k scores while scanning the bucket range from smallest to largest.

Maintain a running window across the bucket values while counting how many elements are currently included. Expand the right boundary until at least k scores are covered, then shrink from the left to maintain the smallest possible range. The difference between bucket indices represents the score spread.

This approach behaves similarly to sliding window but operates on value ranges instead of sorted elements. It becomes efficient when the score range R is small compared to n, though it requires additional memory for the bucket array.

Recommended for interviews: Sorting with a sliding window is the expected solution. It is simple, provably optimal for this problem, and easy to implement under time pressure. Discussing the bucket-based idea shows deeper algorithmic thinking, but interviewers typically look for the sorted window approach first.