632. Smallest Range Covering Elements from K Lists


Problem Description

You are provided k lists which contain sorted integers in non-decreasing order. Your task is to find the smallest range that contains at least one number from each of the k lists. To determine which range is the smallest, you must use the rules given below:

  1. If range [a, b] has a smaller length than range [c, d] (meaning b - a < d - c), then [a, b] is considered smaller.
  2. If the lengths are equal (meaning b - a == d - c), then range [a, b] is considered smaller if a < c.

The objective is to find the smallest such range [a, b] according to the criteria above.

Intuition

To arrive at the solution, consider the following approach:

  • The brute force method would naturally involve checking all possible ranges, which would be prohibitively expensive as it might take O(N^2) time where N is the total number of elements in all lists combined.
  • A better approach is to consider that since the lists are sorted, we can use a sliding window along with a pointer for each list to keep track of whether we have at least one number from each list within our current window.
  • To implement this idea efficiently, we can use a min-heap to keep track of the smallest element outside our current range and a hash map or counter to keep track of the elements within our range.
  • We line up all the elements from all the lists in sorted order with their corresponding list indices, then move the right boundary of our window to include elements, while keeping track of which lists are represented within the window using the counter.
  • When all k lists are represented within the window, we try to minimize the range by moving the left boundary to the right while ensuring that at least one number from each list is still inside the window.
  • Each time we have all k lists represented, we check if the current range is smaller than our best found range. If it is, we update our answer.
  • This gives us an O(NlogN) solution because of the initial sort, and then for each of the N elements, we perform operations that can be considered in constant time on average.

The provided code follows this intuition and finds the smallest range efficiently.

Solution Approach

The code provided implements an efficient solution as follows:

  1. Flatten and Sort: The algorithm starts by flattening all k sorted lists into a single list t and tagging each element with the index of the list it came from. This is done using list comprehension. Then, it sorts this combined list which will allow efficient traversal using a sliding window.

    1t = [(x, i) for i, v in enumerate(nums) for x in v]
    2t.sort()
  2. Initialize Counter and Answer: A Counter is initialized to keep track of how many numbers from each list are within the current window. The starting answer range is set from -infinity to infinity to ensure any valid range found will be smaller than this initial range.

  3. Sliding Window: The algorithm then uses a sliding window technique to find the smallest range. The variable j is the left boundary and b iterating over t is the right boundary.

    1cnt = Counter()
    2ans = [-inf, inf]
    3j = 0
  4. Expand and Shrink Window: As we process each element b from the sorted list t, we increment the count of elements seen from its list (given by v). We try to expand the window until it includes at least one number from every list. We do this by checking if the length of the counter is equal to the number of lists.

    1for b, v in t:
    2    cnt[v] += 1
    3    while len(cnt) == len(nums):  # Shrink the window if possible
    4        # Rest of the code for shrinking the window
  5. Update Smallest Range: If the current window includes at least one number from each list, we check if this window range is smaller than our current smallest range (ans). If it's smaller or starts earlier with the same size, we update the answer.

    1a = t[j][0]
    2x = b - a - (ans[1] - ans[0])
    3if x < 0 or (x == 0 and a < ans[0]):
    4    ans = [a, b]
  6. Remove Left Boundary Elements: To potentially get a smaller range, we advance the left boundary of the window (j). We decrement the count of the left boundary's list number, and if the count falls to zero, we remove it from the counter, in effect narrowing our window until it no longer covers all k lists.

    1w = t[j][1]
    2cnt[w] -= 1
    3if cnt[w] == 0:
    4    cnt.pop(w)
    5j += 1
  7. Return Answer: After processing all elements with this sliding window, the smallest range is stored in ans, which is returned as the result.

The implementation leverages the sorting to line up potential candidates for the range and uses a sliding window with a counter to efficiently find and attempt to minify the range while keeping track of the requirement to have at least one number from each of the k lists.

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we have k = 3 lists of sorted integers:

1List 1: [4, 10, 15]
2List 2: [1, 13, 15]
3List 3: [5, 10, 20]

To find the smallest range which contains at least one number from each list following the steps of the solution approach:

  1. Flatten and Sort: We start by combining and tagging each element with its respective list index:

    1Combined: [(4, 0), (10, 0), (15, 0), (1, 1), (13, 1), (15, 1), (5, 2), (10, 2), (20, 2)]

    After sorting we get:

    1Sorted:    [(1, 1), (4, 0), (5, 2), (10, 0), (10, 2), (13, 1), (15, 0), (15, 1), (20, 2)]
  2. Initialize Counter and Answer: We create a counter and set the starting answer range:

    1Counter: {}
    2Answer Range: [-inf, inf]
  3. Sliding Window: Initialize the sliding window boundaries:

    1Left Boundary (j): 0
    2Right Boundary (to be determined in loop): -
  4. Expand and Shrink Window: We iterate through the sorted elements and expand the window by increasing the count for each tag:

    1Iteration 1 (Element: (1, 1)):
    2Counter: {1: 1}
    3Window: [1, -]
    4
    5Iteration 2 (Element: (4, 0)):
    6Counter: {1: 1, 0: 1}
    7Window: [1, 4]
    8
    9Iteration 3 (Element: (5, 2)):
    10Counter: {1: 1, 0: 1, 2: 1}
    11Window: [1, 5]  // Now we have all 3 lists represented

    Upon finding all lists are represented, we can potentially start to shrink the window from the left to find the smallest range.

  5. Update Smallest Range: Since this is the first window that includes numbers from all lists, we update our answer range:

    1Answer Range: [1, 5]

    We will check the range each time we have a new window containing elements from all lists and update if a smaller range is found.

  6. Remove Left Boundary Elements: Now, we will attempt to shrink our window:

    1Moving Left Boundary from 1 to 4:
    2Counter after decrement: {1: 0, 0: 1, 2: 1}
    3Since the count of number from list 1 is now 0, we remove it, and our window is no longer valid.
    4
    5We continue this sliding window approach for the rest of the elements.

    This process will continue until we've exhausted the sorted list.

  7. Return Answer: Eventually, after sliding the window over the entire sorted list, we get our smallest range, which is [1, 5] in this example.

The final output is the answer range. In this example, the smallest range containing at least one number from each of the k lists would be [1, 5]. This method ensures we have covered all the lists while keeping the range as small as possible.

Python Solution

1from collections import Counter
2from typing import List
3
4class Solution:
5    def smallestRange(self, nums: List[List[int]]) -> List[int]:
6        # Flatten the list of lists with their originating list's index
7        flat_list = [(value, idx) for idx, sublist in enumerate(nums) for value in sublist]
8        flat_list.sort()  # Sort the list of tuples by the numeric value
9      
10        # Counter to maintain the number of times an element from each list appears in the range
11        count = Counter()
12        # Initialize the result with infinity, to find the minimum range later
13        result = [float('-inf'), float('inf')]
14        # Pointer to iterate the flattened list
15        pointer = 0
16      
17        # Iterate through the flattened and sorted list
18        for right_value, origin_list_index in flat_list:
19            # Increase the count for the current list index
20            count[origin_list_index] += 1
21          
22            # If the current range includes at least one element from each list
23            while len(count) == len(nums):
24                # Get the left bound of the current range
25                left_value = flat_list[pointer][0]
26                # Calculate the size difference from the best range found so far
27                size_difference = right_value - left_value - (result[1] - result[0])
28                # Update the result if the current range is smaller, or equally small but starting with a smaller value
29                if size_difference < 0 or (size_difference == 0 and left_value < result[0]):
30                    result = [left_value, right_value]
31                # Get the list index of the left bound of the current range
32                left_origin_index = flat_list[pointer][1]
33                # Decrease the count for this list index
34                count[left_origin_index] -= 1
35                # If count reaches zero, it means we no longer have an element from this list in range
36                if count[left_origin_index] == 0:
37                    # Remove it from count
38                    count.pop(left_origin_index)
39                # Move the left pointer forward
40                pointer += 1
41      
42        # Return the final smallest range found
43        return result
44

Java Solution

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    public int[] smallestRange(List<List<Integer>> nums) {
8        // Count total elements from all the lists
9        int totalElements = 0;
10        for (List<Integer> list : nums) {
11            totalElements += list.size();
12        }
13      
14        // Initialize an array to store elements and their corresponding list indices
15        int[][] elementsWithIndex = new int[totalElements][2];
16        int numLists = nums.size();
17      
18        // Populate the array with elements from the lists
19        for (int i = 0, currentIndex = 0; i < numLists; ++i) {
20            for (int num : nums.get(i)) {
21                elementsWithIndex[currentIndex++] = new int[] {num, i};
22            }
23        }
24      
25        // Sort the array based on the numeric value of elements
26        Arrays.sort(elementsWithIndex, (a, b) -> Integer.compare(a[0], b[0]));
27      
28        Map<Integer, Integer> count = new HashMap<>();
29        int[] answer = new int[] {-1000000, 1000000};
30        int start = 0;
31      
32        // Iterate through the elements to find the smallest range
33        for (int[] elementAndIndex : elementsWithIndex) {
34            int endValue = elementAndIndex[0];
35            int listIndex = elementAndIndex[1];
36          
37            // Increment the count for this list index
38            count.put(listIndex, count.getOrDefault(listIndex, 0) + 1);
39          
40            // While all lists are represented in the current window
41            while (count.size() == numLists) {
42                int startValue = elementsWithIndex[start][0];
43                int startIndex = elementsWithIndex[start][1];
44              
45                // Check if we have found a smaller range
46                int rangeDiff = endValue - startValue - (answer[1] - answer[0]);
47                if (rangeDiff < 0 || (rangeDiff == 0 && startValue < answer[0])) {
48                    answer[0] = startValue;
49                    answer[1] = endValue;
50                }
51              
52                // Decrement the count for this list index and potentially remove it
53                count.put(startIndex, count.get(startIndex) - 1);
54                if (count.get(startIndex) == 0) {
55                    count.remove(startIndex);
56                }
57              
58                // Move the start of the window to the right
59                ++start;
60            }
61        }
62        return answer;
63    }
64}
65

C++ Solution

1class Solution {
2public:
3    vector<int> smallestRange(vector<vector<int>>& nums) {
4        // Calculate the total number of elements.
5        int totalElements = 0;
6        for (auto& group : nums) totalElements += group.size();
7      
8        // Create a vector to store the pair of values and their corresponding group index.
9        vector<pair<int, int>> sortedElements(totalElements);
10      
11        // Total number of groups.
12        int numGroups = nums.size();
13      
14        // Flatten all values along with their group index into sortedElements.
15        for (int i = 0, index = 0; i < numGroups; ++i) {
16            for (int value : nums[i]) {
17                sortedElements[index++] = {value, i};
18            }
19        }
20      
21        // Sort the elements based on values.
22        sort(sortedElements.begin(), sortedElements.end());
23      
24        // Initialize pointers and a map to track the count of each group's presence in the current window.
25        int startWindow = 0;
26        unordered_map<int, int> groupCount;
27      
28        // Initialize the answer with the worst possible range.
29        vector<int> range = {-1000000, 1000000};
30      
31        // Iterate through the sorted elements and find the minimum range that includes at least one number from each group.
32        for (int endWindow = 0; endWindow < totalElements; ++endWindow) {
33            int currentValue = sortedElements[endWindow].first;
34            int currentGroup = sortedElements[endWindow].second;
35          
36            // Add the current value to the count of its group.
37            ++groupCount[currentGroup];
38          
39            // Try to shrink the window from the left if all groups are present in the window.
40            while (groupCount.size() == numGroups) {
41                int windowStartValue = sortedElements[startWindow].first;
42                int windowStartGroup = sortedElements[startWindow].second;
43              
44                // Compare with the current best range and update if necessary.
45                int currentRange = currentValue - windowStartValue;
46                int bestRange = range[1] - range[0];
47                if (currentRange < bestRange || (currentRange == bestRange && windowStartValue < range[0])) {
48                    range[0] = windowStartValue;
49                    range[1] = currentValue;
50                }
51              
52                // Decrease the count of the starting group's element and possibly remove it from the hash map if count becomes zero.
53                if (--groupCount[windowStartGroup] == 0) {
54                    groupCount.erase(windowStartGroup);
55                }
56              
57                // Move the window start forward.
58                ++startWindow;
59            }
60        }
61      
62        // Return the smallest range found.
63        return range;
64    }
65};
66

Typescript Solution

1// Define a function to find the smallest range that includes at least one number from each list.
2function smallestRange(nums: number[][]): number[] {
3    // Calculate the total number of elements across all lists.
4    const totalElements = nums.reduce((acc, group) => acc + group.length, 0);
5
6    // Create an array to store tuples of values and their corresponding list index.
7    const sortedElements: [number, number][] = new Array(totalElements);
8
9    // Flatten all values along with their list index into the `sortedElements` array.
10    let index = 0;
11    for (let i = 0; i < nums.length; ++i) {
12        for (const value of nums[i]) {
13            sortedElements[index++] = [value, i];
14        }
15    }
16
17    // Sort the elements based on the numeric values.
18    sortedElements.sort(([val1], [val2]) => val1 - val2);
19
20    // Initialize the pointers and a Map to track the count of each list's presence in the current window.
21    let startWindow = 0;
22    const groupCount = new Map<number, number>();
23
24    // Initialize the answer with a large possible range.
25    let range: number[] = [-1000000, 1000000];
26
27    // Iterate through the sorted elements to find the minimum range.
28    for (let endWindow = 0; endWindow < totalElements; ++endWindow) {
29        const [currentValue, currentGroup] = sortedElements[endWindow];
30
31        // Update the count of the current group.
32        groupCount.set(currentGroup, (groupCount.get(currentGroup) || 0) + 1);
33
34        // Attempt to shrink the window from the left if all groups are present.
35        while (groupCount.size === nums.length) {
36            const [windowStartValue, windowStartGroup] = sortedElements[startWindow];
37
38            // Update the range if the current one is better.
39            const currentRange = currentValue - windowStartValue;
40            const bestRange = range[1] - range[0];
41            if (currentRange < bestRange || (currentRange === bestRange && windowStartValue < range[0])) {
42                range = [windowStartValue, currentValue];
43            }
44
45            // Decrease the count of the starting group's element and remove it if the count becomes zero.
46            const startGroupCount = groupCount.get(windowStartGroup)! - 1;
47            if (startGroupCount === 0) {
48                groupCount.delete(windowStartGroup);
49            } else {
50                groupCount.set(windowStartGroup, startGroupCount);
51            }
52
53            // Move the window start forward.
54            startWindow++;
55        }
56    }
57
58    // Return the smallest range found.
59    return range;
60}
61

Time and Space Complexity

The given Python code finds the smallest numerical range that includes at least one number from each of the k lists. The approach is a type of sliding window algorithm with two pointers.

Time Complexity

Let's break down the time complexity:

  1. Creating the merged list (t): This involves iterating over each list in nums and each element within those lists. If n is the total number of elements across all k lists, creating the merged list t is O(n).

  2. Sorting the merged list (t.sort()): The sorting step has a time complexity of O(n log n) since it is sorting n elements.

  3. Sliding window over t: The sliding window loop processes each element in t once. Incrementing the second pointer j and checking and updating the counter results in traversing all n elements once. Thus, this part has a time complexity of O(n).

Combining these steps, the dominant term is the sort, and thus the overall time complexity of the code is O(n log n).

Space Complexity

Now, let's consider space complexity:

  1. Merged list (t): The merged list t contains n tuples where n is the total number of elements across all k lists, so space complexity for t is O(n).

  2. Counter (cnt): The counter keeps track of the presence of elements from each list within the current window. In the worst case, it will have k keys where k is the number of lists in nums. Since the space for cnt is dependent on the number of lists and not the number of elements, it's O(k).

  3. Range list (ans): The range list has a constant size of 2, hence O(1).

Thus, the overall space complexity of the algorithm is dominated by the space taken by the merged list t, which is O(n) where n is the total number of elements across all the lists.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫