What is the time complexity of the Brute Force approach?

The Brute Force approach has a time complexity of O(n · 2ⁿ) as it iterates through all 2ⁿ subsets of the array.

What is the time complexity of the Sorting + Sliding Window approach?

The Sorting + Sliding Window approach has a time complexity of O(n log n), dominated by the sorting step.

What is the space complexity of the optimal solution?

The space complexity is O(1) or O(n) depending on the sorting implementation, as we only need to store the minimum difference.

Minimum Difference Between Highest and Lowest of K Scores

Difficulty: Easy | Acceptance: 66.30% | Paid: No Topics: Array, Sliding Window, Sorting

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.

Examples
Constraints
Brute Force
Sorting + Sliding Window

Examples

Example 1

Input:

nums = [90], k = 1

Output:

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:

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⁵

Brute Force

Intuition Generate all possible combinations of k elements from the array and compute the difference between the maximum and minimum in each combination to find the minimum.

Steps

If k equals 1, return 0 since the difference is always 0
Generate all combinations of k elements using bitmask or recursion
For each combination, find the maximum and minimum values
Track the minimum difference across all combinations

python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -&gt; int:
        if k == 1:
            return 0
        
        min_diff = float('inf')
        n = len(nums)
        
        from itertools import combinations
        for combo in combinations(nums, k):
            diff = max(combo) - min(combo)
            min_diff = min(min_diff, diff)
        
        return min_diff

Complexity

Time: O(n · 2ⁿ) - We iterate through all 2ⁿ subsets
Space: O(k) - For storing the current combination
Notes: Exponential time complexity, only works for small n

Sorting + Sliding Window

Intuition After sorting, the optimal k elements must be consecutive. Any non-consecutive selection can be improved by replacing elements to close gaps, so we only need to check all windows of size k.

Steps

If k equals 1, return 0 since the difference is always 0
Sort the array in ascending order
Use a sliding window of size k across the sorted array
For each window, compute the difference between the last and first element
Track and return the minimum difference found

python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -&gt; int:
        if k == 1:
            return 0
        
        nums.sort()
        min_diff = float('inf')
        
        for i in range(len(nums) - k + 1):
            diff = nums[i + k - 1] - nums[i]
            min_diff = min(min_diff, diff)
        
        return min_diff

Complexity

Time: O(n log n) - Dominated by sorting
Space: O(1) or O(n) depending on sorting implementation
Notes: Optimal solution, works efficiently for all constraints