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

Input: You are provided with an integer array nums and an integer k.

Example: nums = [1, 3, 8, 7, 9], k = 3

Constraints:

• 1 <= k <= nums.length <= 1000

• 0 <= nums[i] <= 10^5

Output: Return the minimum possible difference between the highest and the lowest score of the selected k students.

Example: Output: 2

Constraints:

• The returned value must be the smallest possible difference.

Goal: The goal is to select a subset of k students from the array such that the difference between the highest and the lowest score in that subset is minimized.

Steps:

• Sort the array to make the differences easier to calculate.

• Iterate through the sorted array and consider every contiguous subsequence of length k.

• For each subsequence, calculate the difference between the first and the last element, then track the minimum difference.

Goal: The input array can be large, so the algorithm should be efficient.

Steps:

• The solution should handle arrays of up to 1000 elements efficiently.

Assumptions:

• The array is not empty, and k is at least 1.

• Input: Input: nums = [1, 3, 8, 7, 9], k = 3

• Explanation: After sorting the array, we get [1, 3, 7, 8, 9]. Selecting the students with scores 3, 7, and 8 gives a difference of 8 - 3 = 5. The minimum possible difference is 2.

• Input: Input: nums = [5, 2, 9, 4], k = 2

• Explanation: The sorted array is [2, 4, 5, 9]. Choosing the students with scores 4 and 5 results in a difference of 5 - 4 = 1. This is the minimum possible difference.

Approach: We will sort the array of student scores, and then use a sliding window technique to find the smallest possible difference between the highest and lowest scores in any subsequence of length k.

Observations:

• Sorting the array helps because it allows us to consider only consecutive elements for a valid subsequence.

• By sliding a window of size k over the sorted array, we can easily compute the difference between the largest and smallest elements in each subsequence.

Steps:

• Sort the input array nums.

• Iterate through the array with a sliding window of size k.

• For each window, compute the difference between the first and last element and track the minimum difference.

Empty Inputs:

• If the array is empty, return 0 since there are no students to choose.

Large Inputs:

• For large arrays, ensure the algorithm runs in O(n log n) time due to sorting.

Special Values:

• If k equals the length of the array, the only valid choice is the entire array.

Constraints:

• The solution must handle large arrays and ensure that the minimum difference is computed efficiently.

int minimumDifference(vector<int>& nums, int k) {
int res = INT_MAX;
sort(begin(nums), end(nums));
for (int i = k - 1; i < nums.size(); ++i)
    res = min(res, nums[i] - nums[i - k + 1]);
return res;
}

1 : Variable Initialization

int minimumDifference(vector<int>& nums, int k) {

Defines the function `minimumDifference` that takes a vector `nums` and an integer `k`, representing the array and the size of the subarray, respectively.

2 : Variable Initialization

int res = INT_MAX;

Initializes a variable `res` with the maximum possible integer value to keep track of the minimum difference.

3 : Sorting

sort(begin(nums), end(nums));

Sorts the array `nums` in non-decreasing order, which is necessary for efficiently finding the minimum difference in subsequent steps.

4 : Looping

for (int i = k - 1; i < nums.size(); ++i)

Starts a loop from the index `k-1` to iterate through the sorted array `nums` and compare elements that are part of a subarray of size `k`.

5 : Mathematical Operations

    res = min(res, nums[i] - nums[i - k + 1]);

Updates the `res` variable by calculating the minimum difference between the current element `nums[i]` and the element `k` positions before it.

6 : Return Statement

return res;

Returns the minimum difference found between the elements in any subarray of size `k`.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: Sorting the array takes O(n log n) time, and iterating through it takes O(n) time.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) for the sorted array, and O(1) if we are sorting in place.

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

Explore →