Tightest Group of K Scores
EasySliding Window
Problem
A coach has the test scores of every student in scores and must pick exactly k students for a study group whose levels are as similar as possible.
Return the smallest possible difference between the highest and the lowest score among the chosen k students.
Example 1
- Input:
- scores = [15, 3, 11, 8, 20], k = 3
- Output:
- 7
Sorted: [3, 8, 11, 15, 20]. Picking 8, 11, 15 gives 15 - 8 = 7, the smallest spread of any three.
Example 2
- Input:
- scores = [42], k = 1
- Output:
- 0
Constraints
- 1 ≤ k ≤ scores.length ≤ 10^5
- 0 ≤ scores[i] ≤ 10^5
Hint
Show the first hint
Order does not matter for a group. Would sorting help?
Walkthrough
How to approach it
01Clarify before coding
- Is the original order relevant? No, students are picked freely.
- Can scores repeat? Yes, so the answer can be 0.
- k = 1? The spread of one score is 0.
02Brute force
Try every subset of size k and compute max - min.
Cost: C(n, k) subsets: exponential, hopeless beyond tiny inputs.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.