Minimum Difference Between Highest and Lowest of K Scores Python/Java solution

In Python or Java, sort the array using the built-in sort function and iterate from index 0 to n - k. For each index i, compute nums[i + k - 1] - nums[i] and keep the minimum result. This implementation runs in O(n log n) time and requires only a few lines of code.

What is the best approach for Minimum Difference Between Highest and Lowest of K Scores?

Sorting the scores and scanning with a sliding window is the best approach. After sorting, every group of k students appears as a contiguous segment, so you only need to check the difference between nums[i + k - 1] and nums[i]. The time complexity is O(n log n) due to sorting and O(n) for the window scan.

Is Minimum Difference Between Highest and Lowest of K Scores asked at Google/Amazon/Meta?

Problems based on sorting and sliding window patterns frequently appear in interviews at companies like Amazon, Google, and Meta. This specific problem tests recognition of sorted windows and range minimization, a common pattern in array optimization questions.

What data structure is used in Minimum Difference Between Highest and Lowest of K Scores?

The primary data structure is an array. The optimal solution sorts the array and applies a sliding window across k consecutive elements. An alternative approach uses a frequency bucket array to track score counts when the value range is small.

What is the time complexity of Minimum Difference Between Highest and Lowest of K Scores?

The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a sliding window of size k moves across the array in O(n) time. Space complexity is O(1) if sorting in place, or O(n) depending on the language's sorting implementation.

Description Hints 4 Solution Video 4:33

1984. Minimum Difference Between Highest and Lowest of K Scores

Q: Is Minimum Difference Between Highest and Lowest of K Scores easy or hard?

The problem is classified as Easy on LeetCode. The core idea is recognizing that sorting converts the problem into checking consecutive windows of size k. Once that insight is clear, the implementation is straightforward.

Q: How to solve Minimum Difference Between Highest and Lowest of K Scores in O(n)?

True O(n) without constraints is difficult because the values must effectively be ordered. However, if score values lie within a limited range, you can use a bucket or counting approach. Build a frequency array and slide a window across score values while maintaining at least k elements, giving O(n + R) time where R is the score range.

Easy66.2% acceptance5 companies

You are given a 0-indexed integer array nums, where nums[i] represents the score of the i^th student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example 1:

Input: nums = [90], k = 1
Output: 0
Explanation: 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
Explanation: 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] <= 10⁵

Asked at 5 companies

Tinkoff Amazon

Google Microsoft Meta

Topics

Hints open one at a time

Hint 1

For the difference between the highest and lowest element to be minimized, the k chosen scores need to be as close to each other as possible.

Hint 2

What if the array was sorted?

Hint 3

After sorting the scores, any contiguous k scores are as close to each other as possible.

Hint 4

Apply a sliding window solution to iterate over each contiguous k scores, and find the minimum of the differences of all windows.

4:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution