☯Beginner-Friendly Guide 'Minimum Difference Between Highest and Lowest of K Scores' - Problem 1984 (C++, Python, JavaScript)

Managing student data often requires finding patterns or groups that are as similar as possible. This problem challenges you to select a specific number of scores while keeping the spread between the best and worst in that group at a minimum. It is a perfect introduction to how sorting and window-based logic can simplify complex selection tasks.

---

Problem Summary

You're given:

• An array of integers named nums representing student scores.
• An integer k, which is the number of student scores you must pick.

Your goal:

• Find a subset of k scores where the difference between the highest score and the lowest score in that subset is the smallest possible value.

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.

---

Intuition

At first glance, picking any k students seems like it would require checking every possible combination, which is very inefficient. However, notice that to minimize the difference between a high and low score, the scores should be as close to each other as possible on a number line.

The most effective way to bring close numbers together is to sort the array. Once the scores are in ascending order, any group of k students that are adjacent to each other in the sorted list will naturally have the smallest possible range for that specific group.

We use a Sliding Window of size k. Since the array is sorted, the lowest score in any window of size k will always be at the start of the window (index i), and the highest score will always be at the end (index i + k - 1).

---

Walkthrough: Understanding the Examples

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

1. Sort the array: The scores become [1, 4, 7, 9].
2. Initialize Window: We need to look at groups of 2.
3. Window 1: Indices 0 and 1 (scores 1 and 4). Difference: .
4. Window 2: Indices 1 and 2 (scores 4 and 7). Difference: .
5. Window 3: Indices 2 and 3 (scores 7 and 9). Difference: .
6. Result: The minimum difference found is 2.

---

Code Blocks

C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        if (k == 1) return 0;

        // Sorting brings the closest scores together
        sort(nums.begin(), nums.end());

        int minDiff = INT_MAX;

        // Slide a window of size k across the sorted array
        for (int i = 0; i <= nums.size() - k; i++) {
            // The max is at the end of the window, min is at the start
            int currentDiff = nums[i + k - 1] - nums[i];
            minDiff = min(minDiff, currentDiff);
        }

        return minDiff;
    }
};

Python

class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        if k == 1:
            return 0

        # Sort the scores to ensure we compare adjacent values
        nums.sort()

        min_diff = float('inf')

        # Check every contiguous window of size k
        for i in range(len(nums) - k + 1):
            # Difference between the last and first element in the window
            current_diff = nums[i + k - 1] - nums[i]
            min_diff = min(min_diff, current_diff)

        return min_diff

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function(nums, k) {
    if (k === 1) return 0;

    // Numeric sort in JavaScript
    nums.sort((a, b) => a - b);

    let minDiff = Infinity;

    // Slide the window through the sorted array
    for (let i = 0; i <= nums.length - k; i++) {
        const currentDiff = nums[i + k - 1] - nums[i];
        if (currentDiff < minDiff) {
            minDiff = currentDiff;
        }
    }

    return minDiff;
};

---

Key Takeaways

• Sorting as a Preprocessing Step: Many problems involving "minimum difference" or "closest values" become significantly easier once the data is ordered.
• Sliding Window Efficiency: By using a fixed-size window on a sorted array, we reduce the problem complexity to for sorting and for the search.
• Edge Case Handling: Always consider the smallest possible value of k. If k is 1, the difference is always 0 because the highest and lowest score are the same.

---

Final Thoughts

This problem is a classic example of how changing the state of your data (sorting) can turn a difficult combinatorial problem into a simple linear scan. In real-world software engineering, this logic is used in load balancing and resource allocation, where you want to group tasks or servers with similar capacities to ensure the system remains stable and predictable. Mastering the sliding window technique is essential for technical interviews at companies like Google or Amazon.