Minimum Difference Between Highest and Lowest of K Scores — Sort and Fixed Window (LC 1984)

Problem Statement#

LeetCode 1984 — Minimum Difference Between Highest and Lowest of K Scores (Easy)

You are given a 0-indexed integer array nums representing student scores and an integer k. Pick any k students and minimize the difference between the highest and lowest chosen scores. Return that minimum difference.

Constraints:

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= 10^5

Input:  nums = [9, 4, 1, 7], k = 2
Output: 2
Explanation: Sorted [1,4,7,9]. Best pair: [7,9] gives 9-7=2.

Input:  nums = [90], k = 1
Output: 0

Why This Problem Matters#

Despite being rated Easy, this problem encodes a non-obvious mathematical observation: the optimal k elements are always contiguous in sorted order. Candidates who miss this resort to generating all C(n,k) subsets — an exponential approach that fails even for modest n.

The problem appears in real-world scenarios such as selecting a balanced team (minimize skill gap), forming price brackets (minimize range), and load balancing (minimize variance of job sizes). The "sort first, then slide" strategy is a mental model that unlocks an entire class of "pick k elements to minimize some range metric" problems, including harder variants at L3/L4 interviews at Google and Amazon.

The Core Insight#

Claim: the k values minimizing max - min are always adjacent in the sorted array.

Why: suppose the optimal k values are not contiguous after sorting. Then there is some value between two chosen values that was not chosen. Swapping the most extreme chosen value for this middle value would reduce or maintain the max-min difference. Therefore the optimal set is always a contiguous sorted block.

Consequence: sort nums once, then compute:

min over all i in [0, n-k]: nums[i + k - 1] - nums[i]

Each window of size k in the sorted array has minimum nums[i] and maximum nums[i+k-1]. No sliding sum needed — just compare the two endpoints.

Visual Dry Run#

Input: nums = [9, 4, 1, 7], k = 2

Sort: [1, 4, 7, 9]

Answer: 2

Solution (Optimal)#

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

var minimumDifference = function(nums, k) {
    nums.sort((a, b) => a - b);
    let minDiff = Infinity;
 
    for (let i = 0; i + k - 1 < nums.length; i++) {
        const diff = nums[i + k - 1] - nums[i];
        if (diff < minDiff) minDiff = diff;
    }
 
    return minDiff;
};

Time: O(n log n) — sort dominates; window scan is O(n) Space: O(1) — in-place sort, two variables

Common Mistakes#

• Trying all C(n,k) subsets — exponential; the sorted-contiguous observation reduces this to O(n)
• Iterating to n-1 instead of n-k — accessing nums[i + k - 1] goes out of bounds; loop stops at n - k inclusive
• Using n - k - 1 as the last index — misses the last valid window; use range(len(nums) - k + 1)
• Computing the window sum instead of window range — only the endpoints matter for max - min
• Special-casing k == 1 unnecessarily — nums[i] - nums[i] = 0 is handled correctly by the formula

Interview Tips#

• State the contiguity observation before writing code: "After sorting, the optimal k elements are always adjacent — swapping a boundary element for a closer one reduces the range"
• The formula nums[i + k - 1] - nums[i] is the entire solution body after sorting
• Be ready for the follow-up: "What if you want minimum variance?" — requires prefix sums of squares

Follow-up Questions#

• Minimum sum of pairwise differences: compute with prefix sums over sorted contiguous windows
• Minimum variance: requires prefix sums of values and squared values; optimal window still contiguous after sorting
• No duplicate values allowed: deduplicate first, then same window technique
• k equals n: only one window (the entire array); answer is nums[n-1] - nums[0] after sorting

Key Takeaways#

• The optimal k elements for minimizing max - min are always contiguous in sorted order — this converts exponential subset search to a linear scan
• Sort once, slide a fixed window of size k: answer is min(nums[i+k-1] - nums[i]) over all valid i
• Loop bound: i runs from 0 to n - k inclusive — equivalent to range(len(nums) - k + 1)
• k == 1 gives difference 0 (handled by formula); k == n gives a single window over the whole array
• Time O(n log n) dominated by sort; space O(1) — the two-line solution after sorting is all that is needed