Minimum Difference Between Highest and Lowest of K Scores

You are given an array nums of student scores and an integer k. Pick the scores of any k students so that the difference between the highest and lowest picked score is as small as possible. Return that minimum difference. This is LeetCode 1984.

Example 1
Input: nums = [90], k = 1
Output: 0
Example 2
Input: nums = [9, 4, 1, 7], k = 2
Output: 2
Explanation: pick 9 and 7.

How to Think About It

Step 1: Trying every group is far too slow

There are "n choose k" groups of k scores, which explodes quickly.

Step 2: Sort, and the best group is a run of neighbours

After sorting, suppose a best group has lowest score nums[i]. Its highest score is at least nums[i + k - 1], because the group needs k values that are all at least nums[i]. Picking exactly nums[i..i+k-1] reaches that bound. So only groups of k consecutive sorted scores need checking.

Step 3: Slide a window of size k

For each start i, the window's difference is nums[i + k - 1] - nums[i]. Return the smallest.

Walkthrough

nums = [9, 4, 1, 7], k = 2; sorted: [1, 4, 7, 9].

WindowHighest - lowest
[1, 4]3
[4, 7]3
[7, 9]2

Java Solution

With k = 1 every window has one value and the difference is 0, so no special case is needed.

Java
import java.util.Arrays;

public class MinimumDiffBetweenHighestAndLowestOfKScores {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int best = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < nums.length; i++) {
            best = Math.min(best, nums[i + k - 1] - nums[i]); // k neighbours in sorted order
        }
        return best;
    }
}

The original implementation, MinimumDiffBetweenHighestAndLowestOfKScores.java, is on GitHub.

Complexity

  • Time: O(n log n) for the sort.
  • Space: O(1) besides the sort.

Sorting so that the best choice becomes a contiguous run also solves Minimum Operations to Make Array Continuous.