Skip to main content
Talentd

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

EasyArraySliding WindowSorting16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

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.

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] <= 105

Approach Overview

Problem Overview: You receive an array of student scores and an integer k. Choose any k scores such that the difference between the highest and lowest score in that group is as small as possible. Return that minimum difference.

The key observation: once the scores are ordered, the best group of k scores must appear as a contiguous segment in the sorted list. Any non‑contiguous choice would only increase the difference between the minimum and maximum values.

Approach 1: Sorting and Sliding Window (Time: O(n log n), Space: O(1) or O(n) depending on sort)

Start by sorting the scores using a standard sorting algorithm. After sorting, every valid group of k elements appears as a contiguous window. Slide a window of size k from left to right and compute nums[i + k - 1] - nums[i] for each position. Track the minimum difference across all windows.

This works because sorting ensures the smallest value in the window is at the left boundary and the largest at the right boundary. The algorithm performs a single pass after sorting, making the window scan O(n). The technique resembles a classic sliding window over a sorted array. This is the standard and most efficient approach used in interviews.

Approach 2: Dynamic Programming Style Buckets (Time: O(n + R), Space: O(R))

If score values fall within a limited range, you can avoid sorting by using buckets. Create a frequency array where the index represents a score and the value represents how many students have that score. Then simulate collecting k scores while scanning the bucket range from smallest to largest.

Maintain a running window across the bucket values while counting how many elements are currently included. Expand the right boundary until at least k scores are covered, then shrink from the left to maintain the smallest possible range. The difference between bucket indices represents the score spread.

This approach behaves similarly to sliding window but operates on value ranges instead of sorted elements. It becomes efficient when the score range R is small compared to n, though it requires additional memory for the bucket array.

Recommended for interviews: Sorting with a sliding window is the expected solution. It is simple, provably optimal for this problem, and easy to implement under time pressure. Discussing the bucket-based idea shows deeper algorithmic thinking, but interviewers typically look for the sorted window approach first.

Approach 1: Approach 1: Sorting and Sliding Window

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.

Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming Style Buckets

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.

Code

Python

Python

Complexity

Time Complexity: O(n + m) where m is the range covered by `max - min`.

Space Complexity: O(m).

Try this approach in the editor →

Approach 3: 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.

Why do we take the scores of k consecutive students? Because if they are not consecutive, the difference between the maximum and minimum values may remain the same or increase, but it will definitely not decrease. Therefore, we only need to consider the scores of k consecutive students after sorting.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of students.

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sorting and Sliding Window

Time Complexity: O(n log n) due to sorting.

Space Complexity: O(1).

Approach 2: Dynamic Programming Style Buckets

Time Complexity: O(n + m) where m is the range covered by `max - min`.

Space Complexity: O(m).

Sorting + Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Sliding WindowO(n log n)O(1) to O(n)General case; simplest and most common interview solution
Bucket / Frequency WindowO(n + R)O(R)When score values lie within a small bounded range

Video Solution

Minimum Difference Between Highest and Lowest of K Scores - Leetcode Weekly Contest - 1984 Python • NeetCode • 22,158 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.
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.
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.
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.

Ready to solve this problem?

Practice Minimum Difference Between Highest and Lowest of K Scores with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array Partition