# Minimum Difference Between Highest and Lowest of K Scores
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores)
Canonical: https://scaleengineer.com/dsa/problems/minimum-difference-between-highest-and-lowest-of-k-scores
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff)
---
## Problem
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`

# Approaches
## Brute Force: Generating All Combinations
This approach considers every possible group of `k` students and calculates the difference between the highest and lowest scores for each group. The minimum of these differences is the answer. It is a straightforward translation of the problem statement into code but is highly inefficient.
**Time:** O(C(n, k) * k), where `n` is the number of elements in `nums`. `C(n, k)` is the number of combinations, which is `n! / (k! * (n-k)!)`. For each combination, we iterate through its `k` elements to find the min and max. This is highly inefficient and will time out for the given constraints. · **Space:** O(k) to store the current combination in the recursion stack. The depth of the recursion is also `k`.
**Pros:** Conceptually simple and directly follows the problem statement.
**Cons:** Extremely slow due to the combinatorial explosion of generating all subsets.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The core idea is to generate all combinations of `k` scores from the input array `nums`. A recursive helper function with backtracking is a common way to achieve this. For each generated combination of `k` scores, we find the maximum and minimum scores within that combination and calculate their difference. A global variable is used to keep track of the minimum difference found across all combinations. After checking all `C(n, k)` combinations (where `n` is the number of students), this minimum difference is returned.

This method is too slow for the given constraints but demonstrates a direct, albeit naive, solution.

Here is a possible implementation:
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    int minDifference = Integer.MAX_VALUE;

    public int minimumDifference(int[] nums, int k) {
        if (k == 1) {
            return 0;
        }
        generateCombinations(nums, k, 0, new ArrayList<>());
        return minDifference;
    }

    private void generateCombinations(int[] nums, int k, int start, List<Integer> combination) {
        if (combination.size() == k) {
            int minVal = Collections.min(combination);
            int maxVal = Collections.max(combination);
            minDifference = Math.min(minDifference, maxVal - minVal);
            return;
        }

        // Optimization: if remaining elements are not enough, stop.
        if (nums.length - start < k - combination.size()) {
            return;
        }

        for (int i = start; i < nums.length; i++) {
            combination.add(nums[i]);
            generateCombinations(nums, k, i + 1, combination);
            combination.remove(combination.size() - 1); // backtrack
        }
    }
}
```
### Algorithm
*   Initialize a global variable `minDifference` to a very large value.
*   Define a recursive function, say `generateCombinations(nums, k, start, combination)`, to generate all combinations of size `k`.
*   The base case for the recursion is when the `combination` list has `k` elements:
    *   Find the minimum and maximum values in the `combination`.
    *   Calculate the difference: `max - min`.
    *   Update `minDifference = min(minDifference, difference)`.
    *   Return from the recursion.
*   In the recursive step, loop from the `start` index to the end of the `nums` array:
    *   Add the current element `nums[i]` to the `combination`.
    *   Make a recursive call: `generateCombinations(nums, k, i + 1, combination)`.
    *   Backtrack by removing the last element added to the `combination`.
*   Start the process by calling `generateCombinations(nums, k, 0, new empty list)`.
*   Return `minDifference`.

## Optimal Approach: Sorting and Sliding Window
A much more efficient approach involves sorting the array first. The key insight is that to minimize the difference between the highest and lowest scores, the `k` chosen scores must be as close to each other as possible. In a sorted array, such scores will form a contiguous block.
**Time:** O(n log n), where `n` is the number of elements in `nums`. The dominant operation is sorting the array. The subsequent sliding window scan takes O(n) time. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types uses a variant of Quicksort which requires `O(log n)` space on average for the recursion stack.
**Pros:** Very efficient and guaranteed to find the optimal solution.; Simple to implement once the key insight is understood.
**Cons:** Requires modifying the input array by sorting, or using extra space for a sorted copy.
### Explanation
The intuition is that if we have a set of `k` scores, and we replace the highest score with a smaller one (that is still larger than the other `k-1` scores), the difference will decrease. Similarly, replacing the lowest score with a larger one will also decrease the difference. This pushes the optimal set of `k` scores to be a contiguous block in the sorted version of the array.

Therefore, the problem reduces to finding the minimum difference among all contiguous subarrays of size `k` in the sorted array. We can do this by iterating through the sorted array with a sliding window of size `k`.

Here is the implementation in Java:
```java
import java.util.Arrays;

class Solution {
    public int minimumDifference(int[] nums, int k) {
        // If k is 1, the difference is always 0 as we pick one student.
        if (k == 1) {
            return 0;
        }
        
        // Sort the array to bring scores closer to each other.
        Arrays.sort(nums);
        
        int minDifference = Integer.MAX_VALUE;
        
        // Use a sliding window of size k.
        // The window is from index i to i + k - 1.
        for (int i = 0; i <= nums.length - k; i++) {
            // The lowest score in the window is nums[i].
            // The highest score in the window is nums[i + k - 1].
            int currentDifference = nums[i + k - 1] - nums[i];
            
            // Update the minimum difference.
            minDifference = Math.min(minDifference, currentDifference);
        }
        
        return minDifference;
    }
}
```
### Algorithm
*   First, sort the input array `nums` in ascending order.
*   Handle the edge case: if `k` is 1, the difference is always 0, so return 0.
*   Initialize a variable `minDifference` to a very large value (e.g., `Integer.MAX_VALUE`).
*   Iterate through the sorted array using a sliding window of size `k`. The loop runs from index `i = 0` to `n - k`.
*   For each window, the lowest score is `nums[i]` and the highest score is `nums[i + k - 1]` because the array is sorted.
*   Calculate the difference: `diff = nums[i + k - 1] - nums[i]`.
*   Update `minDifference` with the minimum value found so far: `minDifference = Math.min(minDifference, diff)`.
*   After iterating through all possible windows, return `minDifference`.

# Solutions
### Python

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

```

### Java

```java
class Solution {
public
  int minimumDifference(int[] nums, int k) {
    Arrays.sort(nums);
    int ans = 100000;
    for (int i = 0; i < nums.length - k + 1; ++i) {
      ans = Math.min(ans, nums[i + k - 1] - nums[i]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumDifference(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int ans = 1e5;
    for (int i = 0; i < nums.size() - k + 1; ++i)
      ans = min(ans, nums[i + k - 1] - nums[i]);
    return ans;
  }
};

```