632. Smallest Range Covering Elements from K Lists - Detailed Explanation

Problem Statement

You are given k sorted integer lists. Your task is to find the smallest range [left, right] that includes at least one number from each of the k lists.

Constraints:

k == nums.length
1 <= k <= 3500
1 <= nums[i].length <= 50
-10^5 <= nums[i][j] <= 10^5
nums[i] are sorted in ascending order.

Example

Input:

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

Output:

[20, 24]

Explanation:

The smallest range [20, 24] contains at least one element from each list.
[20, 24] covers 20 from List 2, 24 from List 1, and 22 from List 3.

Hints:

Think of the problem as merging k sorted lists and finding the smallest window that includes at least one number from each list.
A min-heap (priority queue) can help track the smallest number while keeping the largest number seen so far.
Use a two-pointer (sliding window) approach to maintain a valid window.

Approach 1: Brute Force (Inefficient Solution)

Idea

Generate all possible ranges that contain at least one element from each list.
Choose the smallest range among them.

Algorithm

Merge all k sorted lists into a single sorted list while keeping track of which list each number came from.
Iterate through this sorted list and for each starting point, expand the range until all k lists are covered.
Update the result if the current range is smaller than the previously found smallest range.

Time Complexity

Merging lists: O(N log N), where N is the total number of elements.
Checking all ranges: O(N^2), as we might check every pair.
Total Complexity: O(N^2), which is too slow for large inputs.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Approach 2: Using Min-Heap (Optimal Solution)

Idea

Maintain a min-heap to track the smallest element across all k lists.
Keep a variable max_value to track the largest number in the heap.
Expand the window by pushing elements from the same list as the removed element.
Continue until all lists have been covered at least once.

Algorithm

Initialize a min-heap, inserting the first element of each list.
Track the maximum value seen in the heap.
Continuously extract the smallest element and insert the next element from the same list.
Update the result if the current range [min_heap_root, max_value] is the smallest seen so far.
Stop when any list runs out of elements.

Time Complexity

Heap operations: O(N log k), where N is the total elements and k is the number of lists.
Overall Complexity: O(N log k).

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Step-by-Step Walkthrough (Heap Execution)

Step	Heap Contents (Min Heap)	max_value	Min Range So Far
1	`[(0,1,0), (4,0,0), (5,2,0)]`	5	[0,5]
2	`[(4,0,0), (5,2,0), (9,1,1)]`	9	[4,9]
3	`[(5,2,0), (9,1,1), (10,0,1)]`	10	[5,10]
4	`[(9,1,1), (10,0,1), (12,1,2)]`	12	[9,12]

Common Mistakes

Forgetting to track max_value: The current max ensures all lists are covered.
Handling duplicates incorrectly: Sorting first helps.
Empty lists: Ensure all lists are non-empty before running the algorithm.

Edge Cases

Scenario	Example Input	Expected Output
All lists have the same elements	`[[1,1,1], [1,1,1], [1,1,1]]`	`[1,1]`
Single list input	`[[1,2,3,4,5]]`	`[1,1]`
Lists with large gaps	`[[1,100,200], [50,150,250], [30,130,230]]`	`[100,150]`

Alternative Variations

Finding Longest Range Covering All Lists
- Instead of the smallest, find the largest range that still covers all lists.
Handling Streaming Data
- Modify the approach to handle continuous incoming elements instead of fixed lists.

Problem	Description
[Leetcode 23: Merge k Sorted Lists]	Uses min-heap to merge lists efficiently.
[Leetcode 378: Kth Smallest Element in a Sorted Matrix]	Uses a min-heap to find the smallest elements.
[Leetcode 295: Find Median from Data Stream]	Uses two heaps to dynamically track a moving median.

Final Thoughts

Min-Heap is the best approach because it efficiently finds the smallest range.
O(N log k) complexity makes it practical for large inputs.
Edge cases should be handled to avoid incorrect results.

TAGS

leetcode

CONTRIBUTOR

Design Gurus Team

GET YOUR FREE

Coding Questions Catalog