Problem Statement in English

You’re given a 0-indexed integer array nums and an integer k.

Choose k scores from nums so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Approach

The minimum possible difference will have to be found between numbers that are close to each other when the array is sorted.

Thus, we can sort the array and then use a sliding window of size k to find the minimum difference between the maximum and minimum values in each window.

And we’re done.

Solution in Python


class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:        
        nums.sort()

        res = inf

        l = 0

        for r in range(len(nums)):
            if r - l + 1 == k:
                res = min(res, nums[r] - nums[l])
                l += 1

        return res

Complexity

  • Time: $O(n \log n)$
    Since we sort the array initially.

  • Space: $O(1)$
    Since we only use a few extra variables.

And we are done.