1984. Minimum Difference Between Highest and Lowest of K Scores

Problem Description

In this task, you are provided with an integer array nums, where each element nums[i] represents the score of the i-th student, and an integer k. The index of the array starts from 0, which means it is 0-indexed. Your objective is to select the scores of k students such that when you calculate the difference between the highest and the lowest scores amongst these k students, this difference is the smallest possible. The function should then return this minimum possible difference.

The challenge can be likened to looking for a subsequence of length k within the array that has the smallest range (i.e., the difference between the maximum and minimum elements of the subsequence is minimal).

Intuition

Given that we want to minimize the difference between the highest and lowest scores after picking k continuous scores, sorting the array can simplify the problem. Once the array is sorted, the k scores that will have the minimum possible difference will always be next to one another.

After sorting, we slide a window of size k across the array and calculate the difference between the first and last elements in this window (essentially the scores of the k students we've picked). The smallest difference found during this sliding window process will be the minimum difference we are seeking. Sorting makes sure that each such window will contain the k smallest consecutive elements and thus potential candidates for the minimum range.

The Python code provided sorts the array and then iterates through the array to find the minimum difference between the scores at indices i + k - 1 and i, which represents the end and start of each window of size k. The min function is used on a generator expression to find and return the smallest difference among all these windows.

Learn more about Sorting and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The solution approach for minimizing the difference between the highest and the lowest of the k scores selected from the array involves the following steps:

Sort the Array: First, we sort the array in increasing order. This is important because we want to ensure that when we pick k contiguous scores from the array, we are getting the smallest possible range (difference between the highest and the lowest score) for that segment.
Sliding Window: Once the array is sorted, instead of looking at every possible combination of k scores (which would be inefficient), we use a sliding window of size k. The sliding window starts at the beginning of the array and moves one position to the right at each step, stopping when the end of the window reaches the end of the array.
Calculate Differences: For each window, calculate the difference between the last and the first elements (nums[i + k - 1] - nums[i]). This difference represents the range of scores within that window of k students. Because the array is sorted, this range is also the difference between the highest and the lowest scores in the selection of k scores.
Find the Minimum Difference: After calculating the differences for each window, we select the minimum difference obtained, which represents the solution to the problem. In Python, this is efficiently done using the min() function applied to a generator expression that iterates through the valid starting indices for the windows (0 to len(nums) - k).

The data structure we principally use is the array (or list in Python), and the algorithm employs the sorting and sliding window techniques. The sorting is typically an O(n log n) operation, and the sliding window traversal of the list is an O(n) operation, making the overall time complexity of this algorithm be O(n log n). Here's part of the code that exemplifies the approach:

1nums.sort()  # Step 1: Sort the array
2# Step 2 and 3: [Sliding window](/problems/sliding_window_maximum) calculation of the minimum difference
3min_diff = min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))

In the min_diff calculation, i represents the start index of the sliding window and i + k - 1 is the end index of the window. The generator expression is used to dynamically create the range values for each window without consuming extra space to store these ranges.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose the input integer array nums is [1, 5, 6, 3, 2, 8] and the integer k is 3. We want to find a subset of k students with the minimum possible difference between the highest and the lowest scores.

Sort the Array: First, we sort nums in increasing order. After sorting, nums becomes [1, 2, 3, 5, 6, 8].
Sliding Window: We then create a sliding window of size k to go through the sorted array. With k = 3, our sliding window will consider the following subsets as it moves from the beginning of the array to the end:
- Window 1: [1, 2, 3]
- Window 2: [2, 3, 5]
- Window 3: [3, 5, 6]
- Window 4: [5, 6, 8]
Calculate Differences: We calculate the difference between the last and the first elements of each window, which represents the score range for that subset.
- Difference for Window 1: 3 - 1 = 2
- Difference for Window 2: 5 - 2 = 3
- Difference for Window 3: 6 - 3 = 3
- Difference for Window 4: 8 - 5 = 3
Find the Minimum Difference: Among all the differences calculated, we find that the minimum difference is 2, which comes from the first window [1, 2, 3]. This means the smallest possible difference between the highest and the lowest of the k scores selected from the array is 2.

The sliding window approach allows us to efficiently find the minimum range without having to explore every possible combination of k elements. By sorting the array first, we guarantee that the elements within any given window are as close together as possible, which is key to finding the subset that minimizes the range. Therefore, the minimum possible difference in this example is 2.

Solution Implementation

1class Solution:
2    def minimum_difference(self, nums: List[int], k: int) -> int:
3        # First, we sort the list of numbers in ascending order.
4        nums.sort()
5
6        # Initialize the minimum difference to a large number.
7        # This will be updated as we find smaller differences.
8        min_diff = float('inf')
9      
10        # Iterate over the list, only going up to the point where
11        # we have at least 'k' elements remaining in the list.
12        for i in range(len(nums) - k + 1):
13            # Calculate the difference between the number at the current index
14            # and the number 'k-1' indices ahead. This difference is the
15            # range of the 'k' elements we are considering.
16            current_diff = nums[i + k - 1] - nums[i]
17          
18            # If the current difference is smaller than the previously stored
19            # minimum difference, update the minimum difference.
20            min_diff = min(min_diff, current_diff)
21      
22        # After checking all possible groups of 'k' elements,
23        # return the smallest difference found.
24        return min_diff
25

1import java.util.Arrays; // Import Arrays class to use the sort method
2
3class Solution {
4    // Method to find the minimum difference between the max and min values in any subarray of k elements
5    public int minimumDifference(int[] nums, int k) {
6        // Sort the array in non-decreasing order
7        Arrays.sort(nums);
8      
9        // Initialize the answer with a large value that is certain to be larger than any possible difference in the array
10        int minDifference = Integer.MAX_VALUE;
11      
12        // Iterate through the array and consider each subarray of size k
13        for (int i = 0; i < nums.length - k + 1; ++i) {
14            // Calculate the difference between the last and the first element of the current subarray
15            int currentDifference = nums[i + k - 1] - nums[i];
16          
17            // Update the minimum difference if the current difference is smaller
18            minDifference = Math.min(minDifference, currentDifference);
19        }
20      
21        // Return the minimum difference found
22        return minDifference;
23    }
24}
25

1#include <vector>
2#include <algorithm> // Include algorithm for std::sort and std::min functions
3
4class Solution {
5public:
6    // Function to calculate the minimum difference between the maximum and minimum
7    // elements of any subsequence of length 'k'.
8    int minimumDifference(vector<int>& nums, int k) {
9        // First ensure the array is sorted in non-decreasing order.
10        std::sort(nums.begin(), nums.end());
11
12        // Initialize an answer variable with a large value.
13        int min_diff = INT_MAX;
14
15        // Loop through the array, considering each subsequence of length 'k'
16        // Ensure that we can form a subsequence of length 'k' by checking the condition
17        // (i + k <= nums.size())
18        for (int i = 0; i + k <= nums.size(); ++i) {
19            // Calculate the difference between the max (nums[i + k - 1]) and min (nums[i])
20            // values in this subsequence 
21            int current_diff = nums[i + k - 1] - nums[i];
22            // Update the minimum difference if the current difference is smaller
23            min_diff = std::min(min_diff, current_diff);
24        }
25
26        // Return the smallest difference found
27        return min_diff;
28    }
29};
30

1/**
2 * This function finds the minimum difference between the largest and the smallest value in any k-sized subset of 'nums'.
3 * @param {number[]} nums - An array of integers.
4 * @param {number} k - An integer representing the size of the subset to consider.
5 * @returns {number} - The minimum difference found among all k-sized subsets of 'nums'.
6 */
7function minimumDifference(nums: number[], k: number): number {
8    // Sort the array in non-decreasing order.
9    nums.sort((a, b) => a - b);
10
11    // Get the length of the number array.
12    const numLength = nums.length;
13
14    // Initialize the answer with the largest possible difference in the sorted array.
15    let minDiff = nums[numLength - 1] - nums[0];
16
17    // Iterate over the array, considering all k-sized windows.
18    for (let i = 0; i + k - 1 < numLength; i++) {
19        // Calculate the difference between the end and start of the current window.
20        let currentDiff = nums[i + k - 1] - nums[i];
21
22        // Update minDiff with the smaller of the two differences.
23        minDiff = Math.min(currentDiff, minDiff);
24    }
25
26    // Return the smallest difference found.
27    return minDiff;
28}
29

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Time and Space Complexity

The given Python code aims to find the minimum difference between the maximum and minimum values within any k elements of a sorted array. The code performs a sort operation on the array and then iterates through the array to find the smallest difference between k consecutive elements. The analysis of the time complexity and space complexity is as follows:

Time Complexity

The time complexity of the code is dictated primarily by the sorting algorithm and the subsequent loop that calculates the minimum difference.

nums.sort(): Sorting an array of n elements generally has a time complexity of O(n log n). Python uses Timsort (a hybrid sorting algorithm derived from merge sort and insertion sort) for its sort function, which also has a worst-case time complexity of O(n log n).
min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1)): This part of the code involves a single for loop that iterates n - k + 1 times, where n is the length of the input array nums. Since k is a constant (with respect to the size of the input array), the iteration is O(n).

Combining these two parts, the overall time complexity is O(n log n + n). In terms of big-O notation, the O(n log n) term dominates, so the final time complexity is O(n log n).

Space Complexity

The space complexity of the code is considered by analyzing the extra space required in addition to the input.

nums.sort(): The sort operation occurs in-place and does not require additional space proportional to the input size (extra constants space might be used, depending on the implementation details of the sort, but this does not scale with input size). Therefore, it does not change the space complexity and is O(1).
min(...): The min operation itself does not require additional space that scales with the input size since the result of nums[i + k - 1] - nums[i] is calculated on the fly for each iteration and does not require storing all values. Hence, the space used is also O(1).

Considering both operations, the overall space complexity of the code is O(1), as no additional space that scales with the size of the input is used.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1984. Minimum Difference Between Highest and Lowest of K Scores

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings