💬 Discord
Sign In
NeetCode #222LC-1984EasySliding Window
← Back to All Problems

#222 · #1984 · Minimum Difference Between Highest and Lowest of K Scores(学生分数的最小差值)

📌 Problem Statement & Constraints

You are given a 0-indexed integer array scores and an integer k. Choose k scores so that the difference between the highest and lowest chosen scores is minimised. Return that minimum difference. Constraints: 1 <= k <= scores.length <= 1000, 0 <= scores[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Sort the scores. In an optimal selection, the k chosen scores are consecutive in sorted order.
  2. Therefore the answer is the minimum of scores[i + k - 1] - scores[i] over all valid i.
  3. Sorting makes this O(n log n) with an O(n) scan.
  4. Choosing non-consecutive values can only increase the spread, so the consecutive-window enumeration is exhaustive.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing all subsets of size k: combinatorial explosion.
  • Using scores[i+k] - scores[i]: the window of k elements spans indices i to i + k - 1.
  • Forgetting the k == 1 case: the difference is 0, and the formula gives scores[i] - scores[i] = 0 correctly.
  • Assuming the answer is scores[-1] - scores[0]: that uses all scores, not exactly k.