You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.
Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.
Return the minimum possible difference.
Example 1:
Input: nums = [90], k = 1 Output: 0 Explanation: There is one way to pick score(s) of one student: - [90]. The difference between the highest and lowest score is 90 - 90 = 0. The minimum possible difference is 0.
Example 2:
Input: nums = [9,4,1,7], k = 2 Output: 2 Explanation: There are six ways to pick score(s) of two students: - [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5. - [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8. - [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2. - [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3. - [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3. - [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6. The minimum possible difference is 2.
Constraints:
1 <= k <= nums.length <= 10000 <= nums[i] <= 105Problem 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.
Sort the array and use a sliding window of size k to find the minimum difference. This approach works because sorting arranges the numbers in non-decreasing order, so the subarray of size k with the minimum difference between the maximum and minimum scores will be contiguous.
The basic steps are:
We first sort the array using `qsort`. Then, by applying a sliding window technique, we iterate through the array to find the minimum difference between the maximum and minimum values within a window of size k. The space complexity is O(1) because the sort is done in-place.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
An alternative approach involves using a frequency array (bucket), preview typical dynamic programming styles, especially useful if the range of scores is small. The idea is to count frequencies of each score, then determine the smallest window in terms of integer value rather than index that includes k students.
The basic steps are:
This approach constructs a frequency array to dynamically track the use of indices over the range of integer values found in `nums`. Using two pointers, we adjust to always ensure at least k students are captured, updating the minimum difference when this condition is maintained.
Python
Time Complexity: O(n + m) where m is the range covered by `max - min`.
Space Complexity: O(m).
We can sort the students' scores in ascending order, then use a sliding window of size k to calculate the difference between the maximum and minimum values in the window, and finally take the minimum of the differences of all windows.
Why do we take the scores of k consecutive students? Because if they are not consecutive, the difference between the maximum and minimum values may remain the same or increase, but it will definitely not decrease. Therefore, we only need to consider the scores of k consecutive students after sorting.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of students.
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Sliding Window | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1). |
| Approach 2: Dynamic Programming Style Buckets | Time Complexity: O(n + m) where m is the range covered by `max - min`. Space Complexity: O(m). |
| Sorting + Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Sliding Window | O(n log n) | O(1) to O(n) | General case; simplest and most common interview solution |
| Bucket / Frequency Window | O(n + R) | O(R) | When score values lie within a small bounded range |
Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python • NeetCode • 21,782 views views
Watch 9 more video solutions →Practice Minimum Difference Between Highest and Lowest of K Scores with our built-in code editor and test cases.
Practice on FleetCode