Find the Smallest Range Covering K Sorted Lists

Question

The candidate is asked to find the smallest range that includes at least one number from each of K sorted lists.

Codemia · Accepted Answer

To solve the problem of finding the smallest range covering K sorted lists, we can utilize a min-heap (or priority queue) to efficiently track the current minimum and maximum values from the lists. The idea is to maintain a sliding window that expands and contracts based on the values we pull from the heap.

1. Initialize a min-heap and insert the first element of each list along with the index of the list and the index of the element in that list.
2. Keep track of the maximum value among the current elements in the heap.
3. Continuously extract the minimum element from the heap and update the range if the current range is smaller than the previously recorded range.
4. If the extracted element has a next element in the same list, insert that next element into the heap and update the maximum value if necessary.
5. Repeat until one of the lists is exhausted.

The time complexity of this approach is O(N log K), where N is the total number of elements across all lists and K is the number of lists. This is because we perform log K operations for each of the N elements when inserting and extracting from the heap. The space complexity is O(K) due to the storage of the heap.

```python
import heapq

def smallest_range(lists):
    min_heap = []
    current_max = float('-inf')
    range_start, range_end = 0, float('inf')

for i in range(len(lists)):
        heapq.heappush(min_heap, (lists[i][0], i, 0))
        current_max = max(current_max, lists[i][0])

while True:
        current_min, list_index, element_index = heapq.heappop(min_heap)
        if current_max - current_min < range_end - range_start:
            range_start, range_end = current_min, current_max

if element_index + 1 == len(lists[list_index]):
            break

next_element = lists[list_index][element_index + 1]
        heapq.heappush(min_heap, (next_element, list_index, element_index + 1))
        current_max = max(current_max, next_element)

return (range_start, range_end)
```

Consider edge cases such as when one or more lists are empty. In such cases, we should return an indication that no valid range exists. Additionally, if all lists contain the same elements, the range will be minimal, so the algorithm should handle this efficiently.

Find the Smallest Range Covering K Sorted Lists

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Snapchat Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string