Minimum Difference Between Highest and Lowest of K Scores [Easy] — Sort + Fixed Window
Sanjeev SharmaAdvertisement
Problem Statement
Return the minimum difference between max and min of any k scores selected.
Input: nums=[90], k=1 → Output: 0
Input: nums=[9,4,1,7], k=2 → Output: 2 ([1,3]→sorted [1,4]→diff=3? or [7,9]→2)
Intuition
Sort and slide a window of size k. The difference is always nums[i+k-1]-nums[i]. Minimum over all windows.
Solutions
Python
def minimumDifference(nums: list[int], k: int) -> int:
nums.sort()
return min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))
C++
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;
}
JavaScript
var minimumDifference = function(nums, k) {
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: O(n log n), Space: O(1)
Advertisement
