LeetCode 1984 - Minimum Difference Between Highest and Lowest of K Scores

The problem asks us to find the minimum possible difference between the highest and lowest scores when selecting exactly k scores from an array of student scores.

leetcodeeasyarraysliding-windowsorting

LeetCode Problem 1984

Difficulty: 🟢 Easy
Topics: Array, Sliding Window, Sorting

Solution

Problem Understanding

The problem asks us to find the minimum possible difference between the highest and lowest scores when selecting exactly k scores from an array of student scores. The input is a 0-indexed integer array nums where each element represents a student's score, and an integer k which is the number of scores to pick. The expected output is a single integer representing the minimum difference achievable between the highest and lowest scores among any k selected scores.

The constraints indicate that nums can have up to 1000 elements and each score can go up to 100,000. This rules out brute-force approaches that attempt to check every combination of k scores since the number of combinations grows exponentially. We also know that k is at least 1, so there will always be a valid subset. Important edge cases include k = 1 (difference is always 0) and arrays that are already sorted or contain repeated numbers.

The key insight here is that the problem is fundamentally about minimizing the spread of k consecutive scores when the array is sorted, which allows us to transform it into a sliding window problem after sorting.

Approaches

Brute Force

A brute-force approach would generate all possible subsets of size k from nums, calculate the difference between the maximum and minimum of each subset, and return the smallest difference found. While correct, this method is extremely inefficient because the number of subsets is combinatorial, specifically $C(n, k)$, which is infeasible for n = 1000.

Optimal Approach

The optimal approach leverages sorting. Once the array is sorted, any group of k consecutive elements will always include the smallest difference for that segment. By sliding a window of length k over the sorted array and computing the difference between the first and last elements of the window, we can efficiently find the minimum difference. Sorting ensures that the largest and smallest elements of each window are at the ends, eliminating the need to compute max and min repeatedly for every combination.

Approach Time Complexity Space Complexity Notes
Brute Force O(n choose k * k) O(k) Generate all subsets of size k and calculate their differences
Optimal O(n log n) O(1) Sort the array and use a sliding window to find the minimal difference

Algorithm Walkthrough

  1. Sort the array nums in ascending order. Sorting ensures that elements close to each other have minimal differences, which is key to finding the smallest possible range of k scores.
  2. Initialize a variable min_diff to a large number, e.g., infinity. This will keep track of the minimum difference encountered.
  3. Iterate with a sliding window of size k from the start of the array to the end. For each window starting at index i, calculate the difference between the last and first elements of the window: nums[i + k - 1] - nums[i].
  4. Update min_diff if the current window's difference is smaller than the previously recorded minimum.
  5. Return min_diff after the loop finishes.

Why it works: Sorting ensures that for any window of length k, the maximum difference occurs between the first and last elements. Sliding through all possible windows guarantees that we examine every possible subset of k consecutive scores. Thus, the minimum difference found is the global minimum for all possible subsets.

Python Solution

from typing import List

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        if k == 1:
            return 0
        
        nums.sort()
        min_diff = float('inf')
        
        for i in range(len(nums) - k + 1):
            diff = nums[i + k - 1] - nums[i]
            min_diff = min(min_diff, diff)
        
        return min_diff

In this Python implementation, we first handle the edge case k = 1 directly. Sorting ensures that the smallest differences between k scores are always found in consecutive subarrays. The loop iterates over all possible windows of length k, computing the difference and updating the minimum. Using float('inf') ensures we start with a value larger than any possible difference.

Go Solution

import "sort"

func minimumDifference(nums []int, k int) int {
    if k == 1 {
        return 0
    }
    
    sort.Ints(nums)
    minDiff := int(^uint(0) >> 1) // initialize to max int
    
    for i := 0; i <= len(nums) - k; i++ {
        diff := nums[i+k-1] - nums[i]
        if diff < minDiff {
            minDiff = diff
        }
    }
    
    return minDiff
}

In Go, we handle k = 1 similarly. We use sort.Ints to sort the array, and int(^uint(0) >> 1) to initialize the maximum integer value. The sliding window logic is identical to Python, iterating over each consecutive k-length window and updating the minimum difference.

Worked Examples

Example 1: nums = [90], k = 1

Step Window Difference min_diff
Initial [90] 90-90=0 inf → 0

Return 0.

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

Sorted array: [1, 4, 7, 9]

i Window Difference min_diff
0 [1,4] 4-1=3 3
1 [4,7] 7-4=3 3
2 [7,9] 9-7=2 2

Return 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; sliding window is O(n)
Space O(1) Sorting in-place, no extra significant space

Sorting is the main cost, and the sliding window pass is linear, making the algorithm very efficient.

Test Cases

# Provided examples
assert Solution().minimumDifference([90], 1) == 0
assert Solution().minimumDifference([9,4,1,7], 2) == 2

# Edge cases
assert Solution().minimumDifference([1,2,3,4,5], 5) == 4  # full array
assert Solution().minimumDifference([1,1,1,1], 2) == 0    # identical elements
assert Solution().minimumDifference([10,100,300,200], 2) == 90 # non-consecutive numbers

# Large k and unordered
assert Solution().minimumDifference([100,1,50,20,30], 3) == 20
Test Why
[90], 1 k=1 edge case, difference is always 0
[9,4,1,7], 2 basic case from prompt
[1,2,3,4,5], 5 selecting entire array
[1,1,1,1], 2 identical elements should return 0
[10,100,300,200], 2 checks unordered array with gaps
[100,1,50,20,30], 3 arbitrary array, medium k

Edge Cases

  1. Single element (k=1): The difference is always 0. Our implementation handles this directly with an early return.
  2. All elements identical: Any subset will also have a difference of 0. Sorting and sliding window logic still works correctly because the difference computation yields 0.
  3. k equals array length: The only valid subset is the entire array. Sorting ensures we correctly compute the difference between the largest and smallest elements. Our sliding window loop also handles this case naturally with len(nums) - k + 1 = 1 iteration.

This approach and implementation robustly handle the full spectrum of possible inputs while remaining efficient.