632. Smallest Range Covering Elements from K Lists - Detailed Explanation
Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!
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]
covers20
from List 2,24
from List 1, and22
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)
, whereN
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
Python3
. . . .
Java Implementation
Java
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)
, whereN
is the total elements andk
is the number of lists. - Overall Complexity:
O(N log k)
.
Python Implementation
Python3
Python3
. . . .
Java Implementation
Java
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.
Related Problems for Further Practice
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
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.

Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.