Problem Description

You have an array nums where each element nums[i] represents the score of the i-th student. Given an integer k, you need to select exactly k students from this array.

Your goal is to choose these k students in such a way that the difference between the highest score and the lowest score among the selected students is as small as possible.

For example, if you have scores [9, 4, 1, 7] and k = 2, you could:

• Select students with scores 9 and 4: difference = 9 - 4 = 5
• Select students with scores 9 and 1: difference = 9 - 1 = 8
• Select students with scores 9 and 7: difference = 9 - 7 = 2
• Select students with scores 4 and 1: difference = 4 - 1 = 3
• Select students with scores 4 and 7: difference = 7 - 4 = 3
• Select students with scores 1 and 7: difference = 7 - 1 = 6

The minimum possible difference would be 2 (by selecting scores 9 and 7).

The solution approach sorts the array first, then checks all possible consecutive windows of size k. This works because after sorting, any k consecutive elements will have the smallest possible range compared to selecting non-consecutive elements. The difference for each window is calculated as nums[i+k-1] - nums[i], and the minimum among all these differences is returned.

Intuition

The key insight is recognizing that to minimize the difference between the highest and lowest scores, we want the selected scores to be as close together as possible.

Imagine the scores scattered on a number line. If we pick k scores randomly, they might be spread far apart. But if we could group them tightly together, the difference between max and min would be smaller.

This leads to an important realization: after sorting the array, the optimal selection must be a consecutive group of k elements. Why? Consider any selection of k elements from a sorted array. If these elements are not consecutive, there are gaps between them. We could replace the highest element with a lower one (filling in a gap) or replace the lowest element with a higher one (filling in a gap), and this would either decrease the difference or keep it the same - it would never increase it.

For example, if we have sorted scores [1, 3, 5, 7, 9] and k = 3:

• Selecting non-consecutive elements like [1, 5, 9] gives difference = 9 - 1 = 8
• But selecting consecutive elements like [5, 7, 9] gives difference = 9 - 5 = 4

Once we understand that we need consecutive elements from a sorted array, the problem becomes straightforward: we slide a window of size k through the sorted array and find which window has the minimum difference between its last and first elements. This is simply nums[i+k-1] - nums[i] for each valid starting position i.

Learn more about Sorting and Sliding Window patterns.

Solution Approach

The implementation follows a straightforward two-step process:

Step 1: Sort the array

nums.sort()

We sort the array in ascending order. This arranges all scores from lowest to highest, enabling us to find consecutive groups of k students with minimal score differences.

Step 2: Sliding Window to find minimum difference

return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

After sorting, we use a sliding window technique:

• The window size is k (we need to select exactly k students)
• For each valid starting position i, the window contains elements from index i to i + k - 1
• The difference for each window is calculated as nums[i + k - 1] - nums[i] (last element minus first element in the window)
• We iterate through all possible windows: i ranges from 0 to len(nums) - k

The expression range(len(nums) - k + 1) ensures we don't go out of bounds. If we have n elements and need windows of size k, the last valid starting position is at index n - k.

For example, with nums = [9, 4, 1, 7] and k = 2:

1. After sorting: [1, 4, 7, 9]
2. Windows:
   • Window at i=0: [1, 4], difference = 4 - 1 = 3
   • Window at i=1: [4, 7], difference = 7 - 4 = 3
   • Window at i=2: [7, 9], difference = 9 - 7 = 2
3. Minimum difference = 2

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) if we don't count the space used by sorting.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works step by step.

Example: nums = [3, 9, 6, 1, 8] and k = 3

Step 1: Sort the array

• Original array: [3, 9, 6, 1, 8]
• After sorting: [1, 3, 6, 8, 9]

Step 2: Check all consecutive windows of size k=3

We'll slide a window of size 3 through the sorted array and calculate the difference for each window:

Window 1: Starting at index 0

• Elements: [1, 3, 6]
• Difference: 6 - 1 = 5

Window 2: Starting at index 1

• Elements: [3, 6, 8]
• Difference: 8 - 3 = 5

Window 3: Starting at index 2

• Elements: [6, 8, 9]
• Difference: 9 - 6 = 3

Step 3: Find the minimum difference

• All differences: [5, 5, 3]
• Minimum difference: 3

Therefore, the optimal selection is [6, 8, 9] with a minimum difference of 3.

Why this works: Notice that if we tried to select non-consecutive elements from the sorted array, like [1, 6, 9], the difference would be 9 - 1 = 8, which is larger than our answer. Any selection that "skips" elements in the sorted array will have a larger range than a consecutive selection that includes those same boundary elements or elements closer together.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the input array nums. This is dominated by the sorting operation nums.sort(), which uses Timsort algorithm with O(n × log n) worst-case time complexity. The subsequent iteration through the array to find the minimum difference takes O(n - k + 1) time, which simplifies to O(n), but this is overshadowed by the sorting step.

The space complexity is O(log n). While the sorting is performed in-place and doesn't require additional space proportional to the input size, the sorting algorithm (Timsort in Python) uses O(log n) space for its recursive call stack during the merge operations. The generator expression min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1)) computes values on-the-fly without storing them, contributing O(1) additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Edge Case: k equals array length

One common pitfall is not handling the case where k equals the length of the array. When k = len(nums), we must select all students, so there's only one possible selection.

Problem Code:

# This might cause issues if not careful with range calculation
return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

Why it's problematic: When k = len(nums), the range becomes range(1), which only gives i = 0. The generator expression works but might not be immediately obvious that it handles this edge case correctly.

Solution:

def minimumDifference(self, nums: List[int], k: int) -> int:
    # Handle edge case explicitly for clarity
    if k == len(nums):
        return max(nums) - min(nums)
  
    nums.sort()
    return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

2. Single Element Selection (k = 1)

Another pitfall is when k = 1. Selecting only one student means there's no "difference" between highest and lowest scores since they're the same student.

Problem: The algorithm would return nums[0] - nums[0] = 0 for all windows, which is correct but might not match problem expectations.

Solution:

def minimumDifference(self, nums: List[int], k: int) -> int:
    # Special case: selecting only one student
    if k == 1:
        return 0
  
    nums.sort()
    return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

3. Empty Generator with Invalid k

If k > len(nums), the range calculation range(len(nums) - k + 1) produces an empty range when the argument is negative or zero, causing the min() function to fail.

Error Example:

# If nums has 3 elements and k = 5
# range(3 - 5 + 1) = range(-1) = empty range
# min() on empty sequence raises ValueError

Solution:

def minimumDifference(self, nums: List[int], k: int) -> int:
    # Validate input
    if k > len(nums):
        raise ValueError("Cannot select more students than available")
    if k <= 0:
        raise ValueError("Must select at least one student")
    if k == 1:
        return 0
      
    nums.sort()
    return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

4. Modifying Original Array

The sort() method modifies the original array in-place, which might not be desired if the original order needs to be preserved elsewhere.

Solution:

def minimumDifference(self, nums: List[int], k: int) -> int:
    # Create a sorted copy to preserve original array
    sorted_nums = sorted(nums)
    return min(sorted_nums[i + k - 1] - sorted_nums[i] 
               for i in range(len(sorted_nums) - k + 1))