Minimum Difference Between Highest and Lowest of K Scores

How it works

When we need to minimize the difference between the highest and lowest values among any k chosen elements, sorting the array first is key. After sorting, the smallest possible range of k elements will always be a contiguous segment. Why? Because picking non-adjacent elements after sorting would only increase the gap between max and min. So, we sort the array and then slide a window of size k across it, tracking the minimum difference between the first and last element of each window.

Steps

1. Sort the input array in ascending order.
2. Initialize two pointers: l = 0 and r = k - 1 to represent a window of size k.
3. Initialize res to infinity to track the minimum difference found.
4. While r is within bounds:
   • Compute nums[r] - nums[l] (the difference between max and min in this window).
   • Update res with the minimum of the current res and this difference.
   • Slide the window by incrementing both l and r.
5. Return res.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Forgetting to Sort the Array First

The sliding window approach only works on a sorted array because it relies on contiguous elements having the minimum possible range. Applying the window on an unsorted array compares arbitrary elements, missing the optimal k-element subset.

Off-by-One Error in Window Size

The window should contain exactly k elements, meaning if l is the left index and r is the right index, then r - l + 1 = k, so r = l + k - 1. Initializing r = k instead of r = k - 1 creates a window of size k + 1, producing incorrect difference calculations.

from typing import List

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        l, r = 0, k - 1
        res = float("inf")
        while r < len(nums):
            res = min(res, nums[r] - nums[l])
            l += 1
            r += 1
        return res

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = k - 1, res = INT_MAX;
        while (r < nums.size()) {
            res = min(res, nums[r] - nums[l]);
            l++;
            r++;
        }
        return res;
    }
};