LeetCode 632: 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
-10⁵ <= nums[i][j] <= 10⁵
nums[i] is sorted in non-decreasing order.

Difficulty: Hard

Tags: array, hash table, greedy, sliding window, sorting, heap (priority queue)

Rating: 97.73%

Solution Approach

The problem can be solved efficiently using a min-heap data structure and a sliding window technique. Here’s how the algorithm works:

Initialize a min-heap with the first element from each list, keeping track of:
- The value
- Which list it came from (list index)
- Position in that list (element index)
Keep track of the maximum value among current elements in consideration
While the heap contains an element from each list:
- Pop the minimum element
- Compare current range (max - min) with best range found so far
- Add the next element from the same list (if available)
Return the smallest range found

Implementation in Python

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # Initialize minheap with first element from each list
        heap = []
        max_val = float('-inf')
        for i, lst in enumerate(nums):
            if lst:
                heappush(heap, (lst[0], i, 0))
                max_val = max(max_val, lst[0])
        
        # Initialize result range
        s, e = 0, float('inf')
        
        # Until any list is exhausted
        while len(heap) == len(nums):
            min_val, list_idx, elem_idx = heappop(heap)
            # Update range if current range is smaller
            if max_val - min_val < e - s:
                s = min_val
                e = max_val
            elif max_val - min_val == e - s and min_val < s:
                s = min_val
                e = max_val
            
            # If there are more elements in current list, add next element
            if elem_idx + 1 < len(nums[list_idx]):
                next_val = nums[list_idx][elem_idx + 1]
                heappush(heap, (next_val, list_idx, elem_idx + 1))
                max_val = max(max_val, next_val)
        
        return [s, e]

Detailed Walkthrough

Let’s walk through Example 1 step by step:

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

Initial State:
- Heap: [(0,1,0), (4,0,0), (5,2,0)]
- max_val: 5
- Current best range: [0, ∞]
First Iteration:
- Pop (0,1,0) from heap
- Add (9,1,1) to heap
- max_val: 9
- Range: [0,9]
Second Iteration:
- Pop (4,0,0) from heap
- Add (10,0,1) to heap
- max_val: 10
- Range: [0,10]
Continue iterations…
Final State:
- After several iterations, we find [20,24] is the smallest range
- It contains:
  - 24 from first list
  - 20 from second list
  - 22 from third list

Complexity Analysis

Time Complexity: $O(n * log(k))$
- n is the total number of elements across all lists
- k is the number of lists
- Each element is pushed/popped from heap once
- Heap operations cost $O(log(k))$
Space Complexity: $O(k)$
- The heap stores at most k elements at any time
- k is the number of lists

Key Insights

Why use a min-heap?
- Efficiently tracks minimum value across k lists
- Maintains sorted order while processing elements
Why track max_val separately?
- Avoids need to search through heap for maximum
- Constant time access to range boundaries
When to update the range?
- When current range is smaller than best found
- When ranges are equal but current starts earlier