Minimum Difference Between Highest and Lowest of K Scores

Easy

Asked by:

28 views

Topics:

ArraysTwo PointersSliding Windows

You are given a 0-indexed integer array nums, where nums[i] represents the score of the i^th 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] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the individual scores, and can the scores be negative?
What is the expected behavior if the input array `nums` is empty or if `k` is larger than the size of the array `nums`?
Is `k` guaranteed to be a valid positive integer (i.e., k >= 1)?
Can the input array `nums` contain duplicate scores, and if so, how should they be handled?
Is the goal to return the minimum difference or the k scores that yield the minimum difference?

Brute Force Solution

Approach

We want to find the smallest difference between the highest and lowest scores within any group of a certain size. The most straightforward way is to look at every single possible group of scores of that size, calculate the difference between the highest and lowest in each group, and then find the smallest of those differences.

Here's how the algorithm would work step-by-step:

First, take the first group of scores. This is simply the first set of scores of the required size.
Find the highest and lowest score in that group.
Calculate the difference between the highest and lowest scores you found.
Remember that difference. This will be our initial smallest difference.
Now, move to the next group of scores. This means shifting our window by one score.
Again, find the highest and lowest score in this new group.
Calculate the difference between the highest and lowest scores in this group.
Compare this new difference with the smallest difference we remembered.
If the new difference is smaller, replace the remembered smallest difference with this new smaller difference.
Keep doing this, shifting the window of scores and calculating differences, until you've checked every possible group of scores of the required size.
Finally, the smallest difference you have remembered is the answer.

Code Implementation

def find_minimum_difference(scores, group_size):
    number_of_scores = len(scores)

    # Handle edge case of too few scores
    if number_of_scores < group_size:
        return -1

    minimum_difference = float('inf')

    for i in range(number_of_scores - group_size + 1):
        current_group = scores[i:i + group_size]

        # Find highest and lowest scores within current group
        highest_score = current_group[0]
        lowest_score = current_group[0]

        for score in current_group:
            if score > highest_score:
                highest_score = score
            if score < lowest_score:
                lowest_score = score

        current_difference = highest_score - lowest_score

        # Update minimum difference if necessary
        if current_difference < minimum_difference:
            minimum_difference = current_difference

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through the input array of size n, creating a sliding window of size k in each iteration. Within each window of size k, we find the minimum and maximum elements. Finding the min/max takes O(k) time. Since we iterate through (n-k+1) windows, the overall time complexity is O((n-k+1)*k). In the worst-case scenario, where k is a significant fraction of n or even equal to n, the complexity simplifies to O(n*k).

Space Complexity

O(1) – The algorithm described only uses a few variables to store the current highest score, lowest score, current difference, and the smallest difference found so far. The amount of memory needed for these variables does not depend on the size of the input array. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The goal is to find the smallest difference between the highest and lowest scores when we only pick a specific number of scores. The key idea is to first arrange all the scores in increasing order, then efficiently check all possible groups of the desired size.

Here's how the algorithm would work step-by-step:

First, organize the scores from smallest to largest.
Now, imagine sliding a window of the desired size across the sorted list of scores. This window represents a group of scores we're considering.
For each position of the window, find the difference between the highest and lowest scores within that window. The highest score is the last score in the window, and the lowest score is the first.
Keep track of the smallest difference you find as you slide the window across all possible positions.
Once you've considered all possible windows, the smallest difference you've tracked is the answer.

Code Implementation

def minimum_difference_between_highest_and_lowest_of_k_scores(scores, k):
    scores.sort()

    minimum_difference = float('inf')

    # Iterate through all possible windows of size k
    for i in range(len(scores) - k + 1):
        # The window represents a group of k scores
        window = scores[i:i+k]

        # Find the difference between the highest and lowest scores in the window
        current_difference = window[-1] - window[0]

        # Update the minimum difference if necessary
        minimum_difference = min(minimum_difference, current_difference)

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this approach is sorting the array of scores, which takes O(n log n) time using efficient sorting algorithms like merge sort or quicksort. The subsequent window sliding operation iterates through the sorted array once. This iteration takes O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place, meaning it modifies the original array directly without creating a new copy. It uses a constant amount of extra space for variables like the minimum difference found so far and the window indices. The space used does not scale with the number of scores N; it remains constant regardless of the input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty scores array	Return infinity or a suitable error value like -1 as no K scores can be selected.
K is larger than the size of the scores array	Return infinity or a suitable error value as it's impossible to select K scores.
K is equal to 1	The minimum difference will always be 0 as we're only selecting one score.
Scores array contains duplicate values	The algorithm should still work correctly and find the minimum difference even with duplicates.
Scores array contains negative numbers	The algorithm should handle negative numbers correctly as it's finding the difference between the highest and lowest, which will be affected by negative values.
Scores array contains a large range of numbers (potential integer overflow)	Use a data type that can accommodate large numbers, such as long, to avoid integer overflow during difference calculations.
Scores array is already sorted	The algorithm should still function correctly, potentially with optimized performance if sorting is used.
Scores array has extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)	Ensure calculations involving these values don't cause overflow or unexpected behavior.

Empty scores array

How to Handle:

Return infinity or a suitable error value like -1 as no K scores can be selected.

K is larger than the size of the scores array

How to Handle:

Return infinity or a suitable error value as it's impossible to select K scores.

K is equal to 1

How to Handle:

The minimum difference will always be 0 as we're only selecting one score.

Scores array contains duplicate values

How to Handle:

The algorithm should still work correctly and find the minimum difference even with duplicates.

Scores array contains negative numbers

How to Handle:

The algorithm should handle negative numbers correctly as it's finding the difference between the highest and lowest, which will be affected by negative values.

Scores array contains a large range of numbers (potential integer overflow)

How to Handle:

Use a data type that can accommodate large numbers, such as long, to avoid integer overflow during difference calculations.

Scores array is already sorted

How to Handle:

The algorithm should still function correctly, potentially with optimized performance if sorting is used.

Scores array has extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Ensure calculations involving these values don't cause overflow or unexpected behavior.