Problem statement

You are given an array nums of student scores and an integer k. Pick the scores of any k students so that the difference between the highest and the lowest of the picked scores is as small as possible.

Return that minimum difference.

Example 1

Input: nums = [90], k = 1
Output: 0

Example 2

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation: Picking 7 and 9 gives a difference of 2.

Example 3

Input: nums = [1,5,6,14,15], k = 3
Output: 5

Constraints

• 1 <= k <= nums.length <= 40
• 0 <= nums[i] <= 100000

Hints for Minimum Difference Between Highest and Lowest of K Scores

1. Hint 1

   The k chosen scores should be as close together as possible — after sorting, that means they are adjacent.

2. Hint 2

   Sort, then slide a window of width k and take the smallest a[i + k - 1] - a[i].

3. Hint 3

   k = 1 always gives 0.

How to solve Minimum Difference Between Highest and Lowest of K Scores

After sorting, the k closest scores are adjacent, so slide a window of width k and take the smallest span.

Approach

1. Return 0 for k <= 1.
2. Sort; for each i, compute a[i + k - 1] - a[i].
3. Return the minimum.

Why it works

Any chosen set of k values spans at least the gap between its min and max; replacing it with the k consecutive sorted values starting at its min can only shrink that gap.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• The window index runs to n - k inclusive.

Reference solution

Python

def minimumDifference(nums, k: int) -> int:
    if k <= 1:
        return 0
    a = sorted(nums)
    return min(a[i + k - 1] - a[i] for i in range(len(a) - k + 1))

Java

public static int minimumDifference(int[] nums, int k) {
    if (k <= 1) return 0;
    int[] a = Arrays.copyOf(nums, nums.length);
    Arrays.sort(a);
    int best = Integer.MAX_VALUE;
    for (int i = 0; i + k <= a.length; i++) {
        best = Math.min(best, a[i + k - 1] - a[i]);
    }
    return best;
}

C++

int minimumDifference(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int best = -1;
    for (int i = 0; i + k <= (int) a.size(); i++) {
        int d = a[i + k - 1] - a[i];
        if (best < 0 || d < best) best = d;
    }
    return best;
}

JavaScript

var minimumDifference = function(nums, k) {
    if (k <= 1) return 0;
    const a = nums.slice().sort(function(x, y) { return x - y; });
    let best = Infinity;
    for (let i = 0; i + k <= a.length; i++) {
        const d = a[i + k - 1] - a[i];
        if (d < best) best = d;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy