Scale Engineer

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
Sliding Window
Algorithms
Sorting
Data structures
Array
Companies
Tinkoff

Prompt

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 <= 1000
  • 0 <= nums[i] <= 105

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:

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    int minDifference = Integer.MAX_VALUE;     public int minimumDifference(int[] nums, int k) {        if (k == 1) {            return 0;        }        generateCombinations(nums, k, 0, new ArrayList<>());        return minDifference;    }     private void generateCombinations(int[] nums, int k, int start, List<Integer> combination) {        if (combination.size() == k) {            int minVal = Collections.min(combination);            int maxVal = Collections.max(combination);            minDifference = Math.min(minDifference, maxVal - minVal);            return;        }         // Optimization: if remaining elements are not enough, stop.        if (nums.length - start < k - combination.size()) {            return;        }         for (int i = start; i < nums.length; i++) {            combination.add(nums[i]);            generateCombinations(nums, k, i + 1, combination);            combination.remove(combination.size() - 1); // backtrack        }    }}

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.

Solutions

class Solution:    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))

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 →

Next problem