Minimum Difference Between Highest and Lowest of K Scores
Problem
You are given an array nums of positive integers and an integer k. Pick any k scores from the array; let the chosen scores have minimum value lo and maximum value hi. Return the minimum possible value of hi − lo.
nums = [9, 4, 1, 7], k = 22def minimum_difference(nums, k):
nums.sort()
best = float('inf')
for i in range(len(nums) - k + 1):
best = min(best, nums[i + k - 1] - nums[i])
return bestfunction minimumDifference(nums, k) {
nums.sort((a, b) => a - b);
let best = Infinity;
for (let i = 0; i + k - 1 < nums.length; i++) {
best = Math.min(best, nums[i + k - 1] - nums[i]);
}
return best;
}class Solution {
public int minimumDifference(int[] nums, int k) {
Arrays.sort(nums);
int best = Integer.MAX_VALUE;
for (int i = 0; i + k - 1 < nums.length; i++) {
best = Math.min(best, nums[i + k - 1] - nums[i]);
}
return best;
}
}int minimumDifference(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int best = INT_MAX;
for (int i = 0; i + k - 1 < (int)nums.size(); i++) {
best = min(best, nums[i + k - 1] - nums[i]);
}
return best;
}Explanation
To make the gap between the highest and lowest chosen score as small as possible, the k scores we pick should be as close together in value as possible. After sorting, close values sit next to each other.
Once sorted, any group of k values that minimizes hi - lo must be k consecutive elements in the sorted order — there's no benefit to skipping around. For a consecutive block, the smallest is its first element and the largest is its last.
So we slide a window of width k across the sorted array and compute nums[i + k - 1] - nums[i] for each start i, keeping the smallest such difference in best.
Example: nums = [9,4,1,7], k = 2. Sorted it is [1,4,7,9]. Adjacent pairs give diffs 3, 3, and 2; the pair (7,9) gives the minimum 2, the answer.
Sorting dominates the cost at O(n log n); the window scan afterward is linear and uses constant extra space.