Minimum Difference Between Highest and Lowest of K Scores - Solution & Explanation

Sort the array and use a sliding window of size k to find the minimum difference. This approach works because sorting arranges the numbers in non-decreasing order, so the subarray of size k with the minimum difference between the maximum and minimum scores will be contiguous.

The basic steps are:

1. Sort the array.
2. Initialize a variable to store the minimum difference and set it to a large number.
3. Slide a window of size k across the sorted array, and for each window, calculate the difference between the highest and lowest numbers found in this window.
4. Keep track of the minimum difference encountered across all windows.
5. Return the minimum difference.

We first sort the array using `qsort`. Then, by applying a sliding window technique, we iterate through the array to find the minimum difference between the maximum and minimum values within a window of size k. The space complexity is O(1) because the sort is done in-place.

An alternative approach involves using a frequency array (bucket), preview typical dynamic programming styles, especially useful if the range of scores is small. The idea is to count frequencies of each score, then determine the smallest window in terms of integer value rather than index that includes k students.

The basic steps are:

1. Create a frequency array large enough to cover the entire range of scores.
2. Count occurrences of each score.
3. Track how many scores are being summed and adjust window size while keeping an exact count of k students.
4. Calculate differences on the go and update the minimum difference as needed.

This approach constructs a frequency array to dynamically track the use of indices over the range of integer values found in `nums`. Using two pointers, we adjust to always ensure at least k students are captured, updating the minimum difference when this condition is maintained.