Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After sorting, an optimal selection can be chosen as k consecutive scores. If a selection skips a score between its minimum and maximum, replacing an extreme with an inside score cannot increase its range. Thus fixed-size sorted windows cover an optimum.

Approach

Sort the scores. For every window of exactly k entries, subtract its first value from its last and keep the minimum difference. Return that minimum. There are no special tie requirements for the selected students, and k = 1 correctly yields zero because the minimum and maximum are the same score.

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        res = inf

        for i in range(k - 1, n):
            mx = nums[i]
            mn = nums[i - (k - 1)]
            res = min(res, mx - mn)

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n) for sorting plus an O(n) fixed-width scan. Auxiliary space: up to O(n) for the runtime's sort workspace.