NeetCode #259LC-632HardSliding Window
← Back to All Problems#259 · #632 · Smallest Range Covering Elements from K Lists(最小区间)
📌 Problem Statement & Constraints
You are given
k sorted lists of integers in nums. Find the smallest range [a, b] such that at least one number from each list lies within it. Constraints: nums.length == k, 1 <= k <= 3500, 1 <= nums[i].length <= 50, each list is sorted ascending.💡 Core Algorithmic Approaches
- Maintain one pointer per list and a min-heap keyed by the current value from each list.
- The current range is
[heap_min, current_max], wherecurrent_maxis tracked separately as the maximum of the pointers seen so far. - Advance the pointer of the list that contributed the minimum, since any smaller range must exclude that minimum.
- The heap gives the minimum in O(log k), and
current_maxis updated with the newly pushed value.
💻 Benchmark Python3 Implementation
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
import heapq
h = [(lst[0], i, 0) for i, lst in enumerate(nums)]
heapq.heapify(h)
cur_max = max(lst[0] for lst in nums)
best = [h[0][0], cur_max]
while True:
val, i, j = heapq.heappop(h)
if j + 1 == len(nums[i]):
break # this list is exhausted -> stop
nxt = nums[i][j + 1]
heapq.heappush(h, (nxt, i, j + 1))
cur_max = max(cur_max, nxt)
if cur_max - h[0][0] < best[1] - best[0]:
best = [h[0][0], cur_max]
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(N log k) where N is the total number of elements: each element is pushed and popped once.
💾 Space Complexity
O(k) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to stop when a list is exhausted: the range must cover all lists, so once any list runs out, no further improvement is possible.
- Tracking
cur_maxasmax(nums[i][j]): the maximum can come from any list, so it must be maintained incrementally as pointers advance. - Recomputing the range from scratch: O(k) per step; the heap front gives the minimum in O(1).
- Assuming the lists have equal length: they do not, so the exhaustion check must be per list.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner