Minimum Difference Between Highest and Lowest of K Scores Problem

Problem

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

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.

Return the minimum possible difference.

Example 1:

1
2
3
4
5
6
7

Input:
nums = [90], k = 1
Output:
 0
Explanation: There is one way to pick score(s) of one student:
- [**90**]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Example 2:

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

Input:
nums = [9,4,1,7], k = 2
Output:
 2
Explanation: There are six ways to pick score(s) of two students:
- [**9**,**4**,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
- [**9**,4,**1**,7]. The difference between the highest and lowest score is 9 - 1 = 8.
- [**9**,4,1,**7**]. The difference between the highest and lowest score is 9 - 7 = 2.
- [9,**4**,**1**,7]. The difference between the highest and lowest score is 4 - 1 = 3.
- [9,**4**,1,**7**]. The difference between the highest and lowest score is 7 - 4 = 3.
- [9,4,**1**,**7**]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.

Examples

Solution

Method 1 – Sorting and Sliding Window

Intuition

To minimize the difference between the highest and lowest scores among any group of k students, we should look for k consecutive scores in the sorted array. Sorting brings closer values together, and a sliding window of size k helps us efficiently find the minimum difference.

Approach

  1. Sort the array of scores in non-decreasing order.
  2. Use a sliding window of size k to consider all possible groups of k consecutive scores.
  3. For each window, compute the difference between the last and first score.
  4. Track the minimum difference found.
  5. Return the minimum difference after checking all windows.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 0; i + k - 1 < nums.size(); ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import "sort"
func minimumDifference(nums []int, k int) int {
    sort.Ints(nums)
    ans := 1 << 31 - 1
    for i := 0; i+k-1 < len(nums); i++ {
        diff := nums[i+k-1] - nums[i]
        if diff < ans {
            ans = diff
        }
    }
    return ans
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < nums.length; i++) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun minimumDifference(nums: IntArray, k: Int): Int {
        nums.sort()
        var ans = Int.MAX_VALUE
        for (i in 0..nums.size - k) {
            ans = minOf(ans, nums[i + k - 1] - nums[i])
        }
        return ans
    }
}
Python
1
2
3
4
5
6
7

class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        nums.sort()
        ans = float('inf')
        for i in range(len(nums) - k + 1):
            ans = min(ans, nums[i + k - 1] - nums[i])
        return ans
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let k = k as usize;
        let mut ans = i32::MAX;
        for i in 0..=nums.len() - k {
            ans = ans.min(nums[i + k - 1] - nums[i]);
        }
        ans
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minimumDifference(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        let ans = Infinity;
        for (let i = 0; i + k - 1 < nums.length; i++) {
            ans = Math.min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of scores, due to sorting.
  • 🧺 Space complexity: O(1) (or O(n) if sorting is not in-place), as only a few variables are used for tracking the answer.