Jobs

Interviews

Discussions

Smallest Range Covering Elements from K Lists

Hard

Asked by:

33 views

Topics:

ArraysGreedy AlgorithmsSliding Windows

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

Smallest Range Covering Elements from K Lists

Hard

Asked by:

33 views

Topics:

ArraysGreedy AlgorithmsSliding Windows

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

Constraints:

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

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 is the range of values within each list, and can the lists contain negative numbers, zeros, or duplicates?
Can any of the K lists be empty, or contain null values?
If there are multiple smallest ranges, is any valid range acceptable, or is there a specific criterion to choose between them?
What should I return if there is no possible range that covers at least one element from each of the K lists?
Are the lists guaranteed to be sorted, and if so, in what order (ascending or descending)?

Brute Force Solution

Approach

The brute force approach to finding the smallest range covering elements from multiple lists is like exhaustively trying every possible range. We consider every possible combination of numbers by taking one number from each list and checking if that range covers all the lists.

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

Select one number from the first list.
Select one number from the second list.
Continue this process, selecting one number from each list until you have one number from every list.
Find the smallest and largest of the numbers you've selected. This defines your range.
Check if this range is smaller than the smallest range you've found so far. If it is, remember this range.
Repeat this entire process by picking all the other possible combinations of numbers from the lists.
After you have checked all the possible ranges, the smallest range you remembered is the answer.

Code Implementation

def smallest_range_brute_force(lists):
    smallest_range_start = -100000
    smallest_range_end = 100000

    # Generate all possible combinations of one element from each list
    def generate_combinations(current_combination, list_index):
        nonlocal smallest_range_start, smallest_range_end
        
        if list_index == len(lists):
            # We have a complete combination, find the range
            minimum_value = min(current_combination)
            maximum_value = max(current_combination)

            # Check if this range is smaller than the current smallest
            if (maximum_value - minimum_value) < (smallest_range_end - smallest_range_start):
                smallest_range_start = minimum_value
                smallest_range_end = maximum_value

            return

        # Iterate through the current list and recurse
        for number in lists[list_index]:
            generate_combinations(current_combination + [number], list_index + 1)

    generate_combinations([], 0)

    return [smallest_range_start, smallest_range_end]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^k) – The brute force solution iterates through every possible combination of numbers, selecting one from each of the k lists. If the lists have lengths n1, n2, ..., nk respectively, the total number of combinations is n1 * n2 * ... * nk. In the worst case where all lists have approximately the same length 'n', the number of combinations becomes n * n * ... * n (k times), which is n^k. For each combination, we find the minimum and maximum, taking O(k) time which doesn't affect the dominant term. Therefore, the overall time complexity is O(n^k).

Space Complexity

O(1) – The brute force approach, as described, considers every possible combination by selecting one number from each list. To find the smallest and largest of the selected numbers for each combination, it only requires storing a fixed number of variables, such as the current smallest number, the current largest number, and the best range found so far. The space required for these variables remains constant regardless of the number of lists or the size of each list. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to solve this is to imagine each list is a conveyor belt of numbers, and you want to pick one number from each belt to form the smallest possible range. We will cleverly advance along these belts, always focusing on reducing the range.

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

First, pick the smallest number from each list. These form your initial range, and also tells you the starting point for the range's width.
Identify the smallest number among the numbers you just picked (one from each list).
Now, advance the 'conveyor belt' that this smallest number came from. Pick the next number from that list to replace the one you just used.
Recalculate the range width using this new set of numbers (one from each list).
Keep doing this: find the smallest number, advance its list, and update the range width.
As you move along, keep track of the narrowest range you have seen so far. Always replace the old range with the new one when you come across a narrower range.
Once you have reached the end of any of the lists, you can stop. The narrowest range you tracked is your answer.

Code Implementation

import heapq

def smallest_range(number_lists):
    number_of_lists = len(number_lists)
    pointers = [0] * number_of_lists
    
    heap = []
    current_max = float('-inf')
    
    # Add the first element of each list to the heap.
    for list_index in range(number_of_lists):
        element = number_lists[list_index][0]
        heapq.heappush(heap, (element, list_index))
        current_max = max(current_max, element)
        
    smallest_range_start = -1
    smallest_range_end = float('inf')

    while True:
        smallest_element, list_index = heapq.heappop(heap)

        # Update the smallest range if the current range is smaller.
        if current_max - smallest_element < smallest_range_end - smallest_range_start:
            smallest_range_start = smallest_element
            smallest_range_end = current_max
        
        pointers[list_index] += 1
        
        # If we've reached the end of a list, we're done.
        if pointers[list_index] == len(number_lists[list_index]):
            break

        next_element = number_lists[list_index][pointers[list_index]]
        heapq.heappush(heap, (next_element, list_index))
        current_max = max(current_max, next_element)
        
    return [smallest_range_start, smallest_range_end]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*k*log(k)) – We iterate until we exhaust one of the k lists. In the worst case, we might iterate through n elements from each list, where n is the maximum length of any list. In each iteration, we find the minimum element among the k current elements from the lists using a min-heap (or similar data structure), which takes O(log k) time. Therefore, the total time complexity is approximately O(n*k*log(k)).

Space Complexity

O(K) – The algorithm maintains a data structure to track the current element from each of the K lists. This could be implemented using a min-heap or a simple array of size K to store the indices or iterators for each list. The space used to store these pointers is directly proportional to the number of lists. Therefore, the auxiliary space complexity is O(K), where K is the number of input lists.

Edge Cases

Case	How to Handle
Input list of lists is null or empty	Return an empty range as there are no elements to cover.
One or more input lists are null or empty	Treat empty lists as if they don't exist to avoid errors during min-heap operations.
All lists contain the same element	The range will be of length 0, consisting of only that element.
Lists contain duplicate elements across different lists	The min-heap approach will correctly handle duplicate elements by considering their positions within their respective lists independently.
Integer overflow when calculating the range (max - min)	Use long data type to store the max and min values, and the range to prevent overflow during calculations.
Maximum-sized input lists causing memory constraints	The algorithm's memory usage is related to K (number of lists), but extreme values can still impact performance; consider splitting large lists into smaller ones if memory becomes a bottleneck.
No solution exists, meaning no possible range covers at least one element from each list.	This scenario is not possible given the problem constraints; there will always be a covering range.
Input lists contain large positive and negative numbers	The algorithm should correctly handle large positive and negative numbers due to standard integer comparison operators.

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 is the range of values within each list, and can the lists contain negative numbers, zeros, or duplicates?
Can any of the K lists be empty, or contain null values?
If there are multiple smallest ranges, is any valid range acceptable, or is there a specific criterion to choose between them?
What should I return if there is no possible range that covers at least one element from each of the K lists?
Are the lists guaranteed to be sorted, and if so, in what order (ascending or descending)?

Brute Force Solution

Approach

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

Select one number from the first list.
Select one number from the second list.
Continue this process, selecting one number from each list until you have one number from every list.
Find the smallest and largest of the numbers you've selected. This defines your range.
Check if this range is smaller than the smallest range you've found so far. If it is, remember this range.
Repeat this entire process by picking all the other possible combinations of numbers from the lists.
After you have checked all the possible ranges, the smallest range you remembered is the answer.

Code Implementation

def smallest_range_brute_force(lists):
    smallest_range_start = -100000
    smallest_range_end = 100000

    # Generate all possible combinations of one element from each list
    def generate_combinations(current_combination, list_index):
        nonlocal smallest_range_start, smallest_range_end
        
        if list_index == len(lists):
            # We have a complete combination, find the range
            minimum_value = min(current_combination)
            maximum_value = max(current_combination)

            # Check if this range is smaller than the current smallest
            if (maximum_value - minimum_value) < (smallest_range_end - smallest_range_start):
                smallest_range_start = minimum_value
                smallest_range_end = maximum_value

            return

        # Iterate through the current list and recurse
        for number in lists[list_index]:
            generate_combinations(current_combination + [number], list_index + 1)

    generate_combinations([], 0)

    return [smallest_range_start, smallest_range_end]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, pick the smallest number from each list. These form your initial range, and also tells you the starting point for the range's width.
Identify the smallest number among the numbers you just picked (one from each list).
Now, advance the 'conveyor belt' that this smallest number came from. Pick the next number from that list to replace the one you just used.
Recalculate the range width using this new set of numbers (one from each list).
Keep doing this: find the smallest number, advance its list, and update the range width.
As you move along, keep track of the narrowest range you have seen so far. Always replace the old range with the new one when you come across a narrower range.
Once you have reached the end of any of the lists, you can stop. The narrowest range you tracked is your answer.

Code Implementation

import heapq

def smallest_range(number_lists):
    number_of_lists = len(number_lists)
    pointers = [0] * number_of_lists
    
    heap = []
    current_max = float('-inf')
    
    # Add the first element of each list to the heap.
    for list_index in range(number_of_lists):
        element = number_lists[list_index][0]
        heapq.heappush(heap, (element, list_index))
        current_max = max(current_max, element)
        
    smallest_range_start = -1
    smallest_range_end = float('inf')

    while True:
        smallest_element, list_index = heapq.heappop(heap)

        # Update the smallest range if the current range is smaller.
        if current_max - smallest_element < smallest_range_end - smallest_range_start:
            smallest_range_start = smallest_element
            smallest_range_end = current_max
        
        pointers[list_index] += 1
        
        # If we've reached the end of a list, we're done.
        if pointers[list_index] == len(number_lists[list_index]):
            break

        next_element = number_lists[list_index][pointers[list_index]]
        heapq.heappush(heap, (next_element, list_index))
        current_max = max(current_max, next_element)
        
    return [smallest_range_start, smallest_range_end]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input list of lists is null or empty	Return an empty range as there are no elements to cover.
One or more input lists are null or empty	Treat empty lists as if they don't exist to avoid errors during min-heap operations.
All lists contain the same element	The range will be of length 0, consisting of only that element.
Lists contain duplicate elements across different lists	The min-heap approach will correctly handle duplicate elements by considering their positions within their respective lists independently.
Integer overflow when calculating the range (max - min)	Use long data type to store the max and min values, and the range to prevent overflow during calculations.
Maximum-sized input lists causing memory constraints	The algorithm's memory usage is related to K (number of lists), but extreme values can still impact performance; consider splitting large lists into smaller ones if memory becomes a bottleneck.
No solution exists, meaning no possible range covers at least one element from each list.	This scenario is not possible given the problem constraints; there will always be a covering range.
Input lists contain large positive and negative numbers	The algorithm should correctly handle large positive and negative numbers due to standard integer comparison operators.