186. Fewest Score Spread
A talent show has collected the judging scores of every contestant in the array scores. The organisers want to put together a final round of exactly k contestants whose scores are as similar as possible, so the round feels fair to everyone in it.
The spread of a group is the highest score in the group minus the lowest score in the group. Choose any k contestants, not necessarily neighbours in the array, and return the smallest spread that can be achieved. If k is 1, the spread of a single contestant is 0.
Example 1
- Input:
- scores = [90,10,40,70,50], k = 3
- Output:
- 30
- Explanation:
Sorted, the scores are 10, 40, 50, 70, 90. The group 40, 50, 70 has spread 30, and no other group of three does better.
Example 2
- Input:
- scores = [5,5,5,9], k = 3
- Output:
- 0
- Explanation:
Three contestants can all score 5, so the spread is 0.
Example 3
- Input:
- scores = [-20,-3,-10], k = 1
- Output:
- 0
- Explanation:
With a single contestant the spread is always 0.
Constraints
1 ≤ k ≤ scores.length ≤ 105
-108 ≤ scores[i] ≤ 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)