LeetCode 632: Smallest Range Covering Elements from K Lists Solution in Python – A Step-by-Step Guide

What Is LeetCode 632: Smallest Range Covering Elements from K Lists?

In LeetCode 632: Smallest Range Covering Elements from K Lists, you’re given k sorted lists of integers, and your task is to find the smallest range [a, b] (inclusive) that contains at least one element from each list, returning the range as [a, b]. The range’s size is b - a, and you minimize this. For example, with [[4, 10, 15], [1, 5, 8], [5, 6, 12]], the smallest range might be [5, 8], covering 15, 5, and 6. Since lists are sorted, we can optimize by tracking boundaries efficiently. This problem tests your ability to manage multiple sequences and minimize intervals.

Problem Statement

• Input:
• nums: A list of k sorted integer arrays.
• Output: A list [a, b]—smallest range covering one element per list.
• Rules:
• Each list is sorted ascending.
• Range must include at least one element from each list.
• Minimize b - a.

Constraints

• 1 ≤ k ≤ 3500.
• 1 ≤ nums[i].length ≤ 50.
• -10⁵ ≤ nums[i][j] ≤ 10⁵.
• Lists are sorted.

Examples

• Input: nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
• Output: [20, 24] (Covers 20, 20, 22; size = 4)
• Input: nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
• Output: [1, 1] (All 1s; size = 0)
• Input: nums = [[10], [11]]
• Output: [10, 11] (Size = 1)

These examples set the stage—let’s solve it!

Understanding the Problem: Finding the Smallest Range

To solve LeetCode 632: Smallest Range Covering Elements from K Lists in Python, we need to find a range [a, b] that includes at least one number from each of k sorted lists, minimizing b - a. A brute-force approach—checking all possible pairs—is O(n² * k), where n is the average list length, impractical for k up to 3500. Since lists are sorted, we can use a sliding window to track the range efficiently. We’ll explore:

• Best Solution (Sliding Window with Min Heap): O(n k log k) time, O(k) space—fast and optimal.
• Alternative Solution (Brute-Force with Sorting): O(n k log(nk)) time, O(nk) space—simpler but slow.

Let’s start with the heap solution, breaking it down for beginners.

Best Solution: Sliding Window with Min Heap

Why This Is the Best Solution

The sliding window with a min heap is the top choice for LeetCode 632 because it’s efficient—O(n * k * log k) time with O(k) space—and leverages a min heap to maintain the smallest range covering all lists in a single pass. It uses the sorted property to slide the window, minimizing recomputation, and fits constraints (k ≤ 3500, n ≤ 50). It’s like sliding a spotlight across lists, keeping the tightest beam!

How It Works

Think of this as a range slider:

• Step 1: Initialize Heap:
• Push first element of each list into a min heap with (value, list_index, element_index).
• Step 2: Track Range:
• Min = heap top, Max = max of initial elements.
• Smallest range = [min, max].
• Step 3: Slide Window:
• Pop min, push next element from its list.
• Update max, compute new range, track smallest.
• Step 4: Stop When Exhausted:
• End when any list runs out.
• Step 5: Return Smallest Range:
• Output [a, b] with min b - a.

It’s like a range finder—slide and minimize!

Step-by-Step Example

Example: nums = [[4, 10, 15], [0, 9, 12], [5, 18, 22]]

• Step 1: Heap = [(0, 1, 0), (4, 0, 0), (5, 2, 0)], Max = 5.
• Step 2: Range = [0, 5], size = 5.
• Step 3: Slide:
• Pop (0, 1, 0), push (9, 1, 1), heap = [(4, 0, 0), (5, 2, 0), (9, 1, 1)], Max = 9.
• Range = [4, 9], size = 5 (no change).
• Pop (4, 0, 0), push (10, 0, 1), heap = [(5, 2, 0), (9, 1, 1), (10, 0, 1)], Max = 10.
• Range = [5, 10], size = 5 (no change).
• Pop (5, 2, 0), push (18, 2, 1), heap = [(9, 1, 1), (10, 0, 1), (18, 2, 1)], Max = 18.
• Range = [9, 18], size = 9 (larger).
• Step 4: Continue, track smallest: [4, 9] remains best.
• Output: [4, 9].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom heapq import heappush, heappop

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # Step 1: Initialize min heap and max value
        k = len(nums)
        heap = []
        curr_max = float('-inf')
        for i in range(k):
            heappush(heap, (nums[i][0], i, 0))  # (value, list_idx, elem_idx)
            curr_max = max(curr_max, nums[i][0])

        # Step 2: Initialize smallest range
        smallest_range = [heap[0][0], curr_max]
        range_size = curr_max - heap[0][0]

        # Step 3: Slide window with heap
        while heap:
            min_val, list_idx, elem_idx = heappop(heap)

            # Update smallest range if current is smaller
            curr_size = curr_max - min_val
            if curr_size < range_size:
                range_size = curr_size
                smallest_range = [min_val, curr_max]

            # Move to next element in this list
            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))
                curr_max = max(curr_max, next_val)
            else:
                break  # Stop if any list is exhausted

        # Step 4: Return smallest range
        return smallest_range

• Line 1: Import heap functions.
• Lines 7-11: Init heap with first elements, track max.
• Lines 14-15: Initial range from min to max.
• Lines 18-30: Slide:
• Pop min, update range, push next, update max.
• Time Complexity: O(n k log k)—n elements per list, k heap ops.
• Space Complexity: O(k)—heap size.

This is like a range scanner—fast and tight!

Alternative Solution: Brute-Force with Sorting

Why an Alternative Approach?

The brute-force with sorting approach merges all elements into one list—O(n * k * log(nk)) time, O(nk) space. It’s simpler, checking all possible ranges, but inefficient for large inputs (k ≤ 3500, n ≤ 50). It’s like laying out all numbers and testing every window!

How It Works

Picture this as a number merger:

• Step 1: Merge lists with list index tags.
• Step 2: Sort by value.
• Step 3: Check all ranges:
• For each start, find end covering all lists, track smallest.
• Step 4: Return result.

It’s like a range tester—exhaustive but slow!

Step-by-Step Example

Example: nums = [[1, 2], [3, 4]]

• Step 1: Merge: [(1, 0), (2, 0), (3, 1), (4, 1)].
• Step 2: Sorted: [(1, 0), (2, 0), (3, 1), (4, 1)].
• Step 3: Check ranges:
• Start 1: End 3 (covers 0, 1), size = 2.
• Start 2: End 3, size = 1 (best so far).
• Step 4: Return [2, 3].
• Output: [2, 3].

Code for Brute-Force Approach

Copy codeclass Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # Step 1: Merge lists with list index
        all_nums = []
        for i, lst in enumerate(nums):
            for num in lst:
                all_nums.append((num, i))

        # Step 2: Sort by value
        all_nums.sort()

        # Step 3: Find smallest range
        k = len(nums)
        count = {}
        left = 0
        min_range = [float('-inf'), float('inf')]
        min_size = float('inf')

        for right in range(len(all_nums)):
            val, idx = all_nums[right]
            count[idx] = count.get(idx, 0) + 1

            while len(count) == k:
                curr_size = all_nums[right][0] - all_nums[left][0]
                if curr_size < min_size:
                    min_size = curr_size
                    min_range = [all_nums[left][0], all_nums[right][0]]
                count[all_nums[left][1]] -= 1
                if count[all_nums[left][1]] == 0:
                    del count[all_nums[left][1]]
                left += 1

        # Step 4: Return result
        return min_range

• Lines 6-9: Merge with indices.
• Line 12: Sort by value.
• Lines 15-31: Slide window, track smallest range.
• Time Complexity: O(n k log(nk))—sorting dominates.
• Space Complexity: O(nk)—merged list.

It’s a range checker—simple but bulky!

Comparing the Two Solutions

• Heap (Best):
• Pros: O(n k log k) time, O(k) space, fast and optimal.
• Cons: Heap logic less intuitive.
• Brute-Force (Alternative):
• Pros: O(n k log(nk)) time, O(nk) space, straightforward.
• Cons: Slower, more space.

Heap wins for efficiency.

Additional Examples and Edge Cases

• Input: [[1], [2]]
• Output: [1, 2].
• Input: [[1, 5], [2]]
• Output: [1, 2].

Both handle these well.

Complexity Breakdown

• Heap: Time O(n k log k), Space O(k).
• Brute-Force: Time O(n k log(nk)), Space O(nk).

Heap is optimal.

Key Takeaways

• Heap: Sliding efficiency—smart!
• Brute-Force: Full scan—clear!
• Ranges: Optimization is fun.
• Python Tip: Heaps rock—see Python Basics.

Final Thoughts: Find That Range

LeetCode 632: Smallest Range Covering Elements from K Lists in Python is a challenging range-finding puzzle. The heap-based sliding window offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 56: Merge Intervals or LeetCode 295: Find Median from Data Stream. Ready to range? Head to Solve LeetCode 632 on LeetCode and find that smallest range today!