algoadvance

Leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores

Problem Statement

You are given a list of integers nums representing the scores of students in a class and an integer k. Your goal is to find the minimum possible difference between the highest and lowest scores among any k students.

Clarifying Questions

1. What are the constraints on the sizes of nums and k?
2. Can k be larger than the length of nums?
3. What kind of values can nums have (positive, negative, or zero)?
4. Are the integers in nums guaranteed to be unique?

For this problem, let’s assume:

• 2 <= k <= nums.size() <= 1000.
• nums contains positive integers.
• The elements in nums are not necessarily unique.

Strategy

The main strategy here is to sort the array and then use a sliding window of size k to find the minimum difference between the maximum and minimum elements in the window.

1. Sort the array: Sorting the array allows us to efficiently find the minimum difference by comparing only consecutive subarrays.
2. Sliding window: Use a sliding window of size k to traverse the sorted array and keep track of the minimum difference between the highest and lowest scores in the window.

Code

#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    int minimumDifference(std::vector<int>& nums, int k) {
        // Sort the array
        std::sort(nums.begin(), nums.end());
        
        // Initialize the minimum difference to a large value
        int min_diff = INT_MAX;
        
        // Iterate through the sorted list using a sliding window of size k
        for (int i = 0; i <= nums.size() - k; ++i) {
            int current_diff = nums[i + k - 1] - nums[i];
            min_diff = std::min(min_diff, current_diff);
        }
        
        return min_diff;
    }
};

// Example usage:
int main() {
    Solution sol;
    std::vector<int> nums = {90, 100, 78, 89, 67, 56, 89, 120};
    int k = 3;
    std::cout << sol.minimumDifference(nums, k) << std::endl; // Output should be the minimum difference
    return 0;
}

Explanation

1. Sorting the array: This is performed to bring close numbers together, which makes it easy to find the minimum difference by comparing only k consecutive elements.
2. Sliding window: After sorting, iterate through the array from the start to the point where a window of size k can still fit. Calculate the difference between the maximum and minimum in the current window and update the minimum difference found so far.

Time Complexity

• Sorting the array takes (O(n \log n)), where (n) is the number of elements in nums.
• Iterating through the array with a sliding window takes (O(n - k)), which is essentially (O(n)).
• Overall, the time complexity is dominated by the sorting step, so it is (O(n \log n)).

This approach efficiently finds the minimum possible difference between the highest and lowest scores among any k students.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?