Minimum Difference Between Highest and Lowest of K Scores

We need to pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Understanding the Problem

We are given an array of integers representing the scores of students. We want to pick k scores and minimize the difference between the highest and lowest of those k scores.

Solution Approach

  1. Sort the Array: To easily find the minimum difference between k elements, first, sort the array.

  2. Slide a Window of Size k: Now, slide a window of size k through the sorted array and calculate the difference between the largest and smallest elements in that window. Keep track of the minimum difference found so far.

  3. Return the Result: Return the minimum difference.

The code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        # Sort the array to easily find the minimum difference
        nums.sort()

        # Initialize the minimum difference variable with a large value
        min_difference = float('inf')

        # Iterate through the array, and for each window of size k, calculate the difference
        for i in range(len(nums) - k + 1):
            difference = nums[i + k - 1] - nums[i]
            min_difference = min(min_difference, difference)

        return min_difference

Key Takeaways

  • Sorting the array simplifies the process of finding the minimum difference between k elements.
  • By sliding a window of size k through the sorted array, we can easily calculate the difference between the largest and smallest elements in that window.
  • The minimum difference among all such windows is our final result.

The given code meets the constraints and efficiently calculates the desired minimum difference.