#1984

Easy

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Minimum Difference Between Highest and Lowest of K Scores

Minimize the difference between the highest and lowest of k student scores using a sliding window approach.

Problem Statement

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k. Your task is to pick the scores of any k students such that the difference between the highest and lowest of the k scores is minimized.

Return the minimum possible difference between the highest and lowest scores when selecting k students from the list.

Examples

Example 1

Input: nums = [90], k = 1

Output: 0

There is one way to pick score(s) of one student:

[90]. The difference between the highest and lowest score is 90 - 90 = 0. The minimum possible difference is 0.

Example 2

Input: nums = [9,4,1,7], k = 2

Output: 2

There are six ways to pick score(s) of two students:

[9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
[9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
[9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
[9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
[9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
[9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6. The minimum possible difference is 2.

Constraints

1 <= k <= nums.length <= 1000
0 <= nums[i] <= 105

Solution Approach

Sort the Array

Begin by sorting the nums array. Sorting ensures that any consecutive k elements will have the smallest possible difference, which is key to minimizing the gap between the highest and lowest scores.

Use Sliding Window

After sorting, use a sliding window of size k to traverse the array. For each window, calculate the difference between the first and last element, which represents the highest and lowest scores in that window.

Track the Minimum Difference

As you slide the window from start to end, keep track of the minimum difference encountered between the highest and lowest score within any window.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n) time, and sliding the window through the array takes O(n). Thus, the overall time complexity is O(n log n), where n is the length of the input array. The space complexity is O(1) if sorting is done in place.

What Interviewers Usually Probe

Candidate demonstrates understanding of sliding window technique and its connection to minimizing the difference in a sorted array.
Solution approach emphasizes sorting and sliding window to reduce complexity, rather than brute force or nested loops.
Candidate considers edge cases, such as when k is 1, and how the window behaves in different scenarios.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array first, which would lead to incorrect results when selecting elements.
Misunderstanding the sliding window concept, resulting in inefficient solutions or wrong windows being chosen.
Incorrectly handling cases where k is equal to the length of the array, which may require special consideration.

Follow-up variants

Adjust the problem to find the minimum difference between highest and lowest for a subset of students based on different conditions.
Extend the problem to find the difference for multiple windows or across multiple groups of k students.
Modify the problem to allow for picking non-consecutive scores to minimize the difference.

FAQ

What is the optimal approach to solve Minimum Difference Between Highest and Lowest of K Scores?

The optimal approach is to sort the array and use a sliding window of size k to find the minimum difference between the highest and lowest scores.

How does the sliding window technique apply to this problem?

The sliding window technique is used to efficiently check all consecutive subarrays of length k, minimizing the difference between the highest and lowest scores.

What happens when k is equal to 1 in this problem?

When k is 1, the difference between the highest and lowest scores is always 0, as there is only one score being considered.

Can the problem be solved using brute force?

While brute force is possible, it would be inefficient. Sorting and sliding window techniques provide a much more optimal solution with reduced time complexity.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, and the space complexity is O(1) if sorting is done in place.

terminal

Solution

Solution 1: Sorting + Sliding Window

We can sort the students' scores in ascending order, then use a sliding window of size $k$ to calculate the difference between the maximum and minimum values in the window, and finally take the minimum of the differences of all windows.

1

2

3

4

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

Continue Practicing

#1838 frequency of the most frequent element #2271 maximum white tiles covered by a carpet #1610 maximum number of visible points