Smallest Range Covering Elements from K Lists
Problem Description
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
- -105 <= nums[i][j] <= 105
- nums[i] is sorted in non-decreasing order.
Solve it on LeetCode
Approaches
1. Priority Queue (Heap) Approach
Intuition:
The problem requires finding the smallest range that includes at least one number from each of K lists. We can use a min-heap to efficiently track the smallest current number across all lists and try to widen our range by tracking maximum elements simultaneously.
- Initialize a min-heap and add the first element of each list along with its index.
- Track the current maximum number across list frontrunners.
- Expand the smallest number (from the heap) by pulling the next element from the same list.
- Update and check the range every time the heap is updated.
Code:
- Time Complexity: O(N log K), where N is the total number of elements across all lists and K is the number of lists. The heap operations (insert, delete) are log K, performed N times.
- Space Complexity: O(K), where K is the number of lists. This is due to storing one element from each list in the heap.
2. Two Pointers with Sorted List
Intuition:
By flattening all lists into a single sorted list while keeping track of their origins, we can use a two-pointer technique to identify the smallest range covering all lists.
- Flatten the list with additional information to identify elements' origin.
- Use two pointers to scan through the list and check complete coverage.
- Attempt to shrink the range by moving the left pointer once coverage is ensured.
Code:
- Time Complexity: O(N log N), where N is the total number of elements across all lists due to the sorting process.
- Space Complexity: O(N), because we store all elements with their list indices and frequency map.