Minimum Difference Between Highest And Lowest Of K Scores - Leetcode Solution

The problem statement is as follows:

Given an array of n integers nums and a positive integer k, find the minimum value of max(nums[i], nums[i+1], ..., nums[i+k-1]) - min(nums[i], nums[i+1], ..., nums[i+k-1]) over all (not empty) subarrays of nums of length k.

To solve this problem, we can use a sliding window approach.

We first initialize two pointers, left and right, pointing to the first element in the array.

Then, we create a variable called diff as the difference between the max and min of the first k elements in the array.

We then loop through the array starting from index k, and in each iteration, we move the left pointer one step to the right and the right pointer one step to the right as well.

We then calculate the difference between the max and min of the current subarray of length k using the following formula:

max_val = max(max_val, nums[right]) min_val = min(min_val, nums[left-1]) cur_diff = max_val - min_val

We update the diff variable if cur_diff is smaller than diff.

Finally, we return the diff variable as the result.

Here's the Python code for the above approach:

def minimumDifference(nums, k): n = len(nums) nums.sort() left, right = 0, k-1 diff = float("inf") while right < n: max_val = nums[right] min_val = nums[left] cur_diff = max_val - min_val diff = min(diff, cur_diff) left += 1 right += 1 return diff

Time Complexity: O(nlogn) due to the sort operation. The while loop runs for n-k+1 times, and each iteration takes O(1) time.

Space Complexity: O(1) as we are using constant extra space.

Overall, this approach is efficient and gives the correct output for the given problem.

1