⚡Flashcard Drill➔
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

  1. Maintain one pointer per list and a min-heap keyed by the current value from each list.
  2. The current range is [heap_min, current_max], where current_max is tracked separately as the maximum of the pointers seen so far.
  3. Advance the pointer of the list that contributed the minimum, since any smaller range must exclude that minimum.
  4. The heap gives the minimum in O(log k), and current_max is 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_max as max(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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems