Minimum Difference Between Highest and Lowest of K Scores

Easy

#1808Time: O(C(n, k) * k), where `n` is the number of elements in `nums`. `C(n, k)` is the number of combinations, which is `n! / (k! * (n-k)!)`. For each combination, we iterate through its `k` elements to find the min and max. This is highly inefficient and will time out for the given constraints.Space: O(k) to store the current combination in the recursion stack. The depth of the recursion is also `k`.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

You are given a 0-indexed integer array nums, where nums[i] represents the score of the i^th 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 <= 1000
0 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach considers every possible group of k students and calculates the difference between the highest and lowest scores for each group. The minimum of these differences is the answer. It is a straightforward translation of the problem statement into code but is highly inefficient.

Algorithm

Initialize a global variable minDifference to a very large value.
Define a recursive function, say generateCombinations(nums, k, start, combination), to generate all combinations of size k.
The base case for the recursion is when the combination list has k elements:
- Find the minimum and maximum values in the combination.
- Calculate the difference: max - min.
- Update minDifference = min(minDifference, difference).
- Return from the recursion.
In the recursive step, loop from the start index to the end of the nums array:
- Add the current element nums[i] to the combination.
- Make a recursive call: generateCombinations(nums, k, i + 1, combination).
- Backtrack by removing the last element added to the combination.
Start the process by calling generateCombinations(nums, k, 0, new empty list).
Return minDifference.

Walkthrough

The core idea is to generate all combinations of k scores from the input array nums. A recursive helper function with backtracking is a common way to achieve this. For each generated combination of k scores, we find the maximum and minimum scores within that combination and calculate their difference. A global variable is used to keep track of the minimum difference found across all combinations. After checking all C(n, k) combinations (where n is the number of students), this minimum difference is returned.

This method is too slow for the given constraints but demonstrates a direct, albeit naive, solution.

Here is a possible implementation:

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    int minDifference = Integer.MAX_VALUE;7 8    public int minimumDifference(int[] nums, int k) {9        if (k == 1) {10            return 0;11        }12        generateCombinations(nums, k, 0, new ArrayList<>());13        return minDifference;14    }15 16    private void generateCombinations(int[] nums, int k, int start, List<Integer> combination) {17        if (combination.size() == k) {18            int minVal = Collections.min(combination);19            int maxVal = Collections.max(combination);20            minDifference = Math.min(minDifference, maxVal - minVal);21            return;22        }23 24        // Optimization: if remaining elements are not enough, stop.25        if (nums.length - start < k - combination.size()) {26            return;27        }28 29        for (int i = start; i < nums.length; i++) {30            combination.add(nums[i]);31            generateCombinations(nums, k, i + 1, combination);32            combination.remove(combination.size() - 1); // backtrack33        }34    }35}

Complexity

Time

O(C(n, k) * k), where `n` is the number of elements in `nums`. `C(n, k)` is the number of combinations, which is `n! / (k! * (n-k)!)`. For each combination, we iterate through its `k` elements to find the min and max. This is highly inefficient and will time out for the given constraints.

Space

O(k) to store the current combination in the recursion stack. The depth of the recursion is also `k`.

Trade-offs

Pros

Conceptually simple and directly follows the problem statement.

Cons

Extremely slow due to the combinatorial explosion of generating all subsets.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.

A much more efficient approach involves sorting the array first. The key insight is that to minimize the difference between the highest and lowest scores, the k chosen scores must be as close to each other as possible. In a sorted array, such scores will form a contiguous block.

Algorithm

First, sort the input array nums in ascending order.
Handle the edge case: if k is 1, the difference is always 0, so return 0.
Initialize a variable minDifference to a very large value (e.g., Integer.MAX_VALUE).
Iterate through the sorted array using a sliding window of size k. The loop runs from index i = 0 to n - k.
For each window, the lowest score is nums[i] and the highest score is nums[i + k - 1] because the array is sorted.
Calculate the difference: diff = nums[i + k - 1] - nums[i].
Update minDifference with the minimum value found so far: minDifference = Math.min(minDifference, diff).
After iterating through all possible windows, return minDifference.

Walkthrough

The intuition is that if we have a set of k scores, and we replace the highest score with a smaller one (that is still larger than the other k-1 scores), the difference will decrease. Similarly, replacing the lowest score with a larger one will also decrease the difference. This pushes the optimal set of k scores to be a contiguous block in the sorted version of the array.

Therefore, the problem reduces to finding the minimum difference among all contiguous subarrays of size k in the sorted array. We can do this by iterating through the sorted array with a sliding window of size k.

Here is the implementation in Java:

1import java.util.Arrays;2 3class Solution {4    public int minimumDifference(int[] nums, int k) {5        // If k is 1, the difference is always 0 as we pick one student.6        if (k == 1) {7            return 0;8        }9        10        // Sort the array to bring scores closer to each other.11        Arrays.sort(nums);12        13        int minDifference = Integer.MAX_VALUE;14        15        // Use a sliding window of size k.16        // The window is from index i to i + k - 1.17        for (int i = 0; i <= nums.length - k; i++) {18            // The lowest score in the window is nums[i].19            // The highest score in the window is nums[i + k - 1].20            int currentDifference = nums[i + k - 1] - nums[i];21            22            // Update the minimum difference.23            minDifference = Math.min(minDifference, currentDifference);24        }25        26        return minDifference;27    }28}

Complexity

Time

O(n log n), where `n` is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent sliding window scan takes O(n) time.

Space

O(log n) or O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types uses a variant of Quicksort which requires `O(log n)` space on average for the recursion stack.

Trade-offs

Pros

Very efficient and guaranteed to find the optimal solution.
Simple to implement once the key insight is understood.

Cons

Requires modifying the input array by sorting, or using extra space for a sorted copy.

Solutions

Solution

1class Solution:2    def minimumDifference(self, nums: List[int], k: int) -> int: nums . sort() return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

1class Solution {2public3  int minimumDifference(int[] nums, int k) {4    Arrays.sort(nums);5    int ans = 100000;6    for (int i = 0; i < nums.length - k + 1; ++i) {7      ans = Math.min(ans, nums[i + k - 1] - nums[i]);8    }9    return ans;10  }11}

1class Solution {2public:3  int minimumDifference(vector<int> &nums, int k) {4    sort(nums.begin(), nums.end());5    int ans = 1e5;6    for (int i = 0; i < nums.size() - k + 1; ++i)7      ans = min(ans, nums[i + k - 1] - nums[i]);8    return ans;9  }10};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem