HeapProblem 11 of 18

Smallest range in K Lists

Brute Force
Time: O(N*K log(N*K))
Space: O(N*K)
Optimal
Time: O(N*K log K)
Space: O(K)

Problem Statement

Given K sorted lists of integers, find the smallest range that includes at least one element from each of the K lists.

Example:

  • Input: lists = [[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
    • List 2: [0, 9, 12, 20], 20 is in range
    • List 3: [5, 18, 22, 30], 22 is in range
    • Range [20, 24] covers all three lists with minimum span

Approach 1: Check All Possible Ranges (Brute Force)

Intuition

For each element in each list, consider it as the start of the range. Find the minimum range that includes at least one element from every other list.

Algorithm

  1. Flatten all lists and sort by value
  2. Use sliding window to find minimum range containing K different lists
  3. Track which lists are covered in current window
java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> elements = new ArrayList<>(); // {value, list index}
        
        int k = nums.size();
        
        // Flatten all lists
        for (int i = 0; i < k; i++) {
            for (int num : nums.get(i)) {
                elements.add(new int[]{num, i});
            }
        }
        
        // Sort by value
        elements.sort((a, b) -> a[0] - b[0]);
        
        int n = elements.size();
        int[] count = new int[k];
        int listsInRange = 0;
        int left = 0;
        
        int minRange = Integer.MAX_VALUE;
        int rangeStart = 0, rangeEnd = 0;
        
        for (int right = 0; right < n; right++) {
            // Add element
            int listIdx = elements.get(right)[1];
            if (count[listIdx] == 0) {
                listsInRange++;
            }
            count[listIdx]++;
            
            // Shrink window
            while (listsInRange == k) {
                int currentRange = elements.get(right)[0] - elements.get(left)[0];
                
                if (currentRange < minRange) {
                    minRange = currentRange;
                    rangeStart = elements.get(left)[0];
                    rangeEnd = elements.get(right)[0];
                }
                
                int leftListIdx = elements.get(left)[1];
                count[leftListIdx]--;
                if (count[leftListIdx] == 0) {
                    listsInRange--;
                }
                left++;
            }
        }
        
        return new int[]{rangeStart, rangeEnd};
    }
}

Complexity Analysis

  • Time Complexity: O(NK log(NK)) - Sorting all elements
  • Space Complexity: O(N*K) - Storing all elements

Approach 2: Min-Heap (Optimal)

Intuition

Maintain pointers to one element from each list. The range is from minimum to maximum of current elements. Use min-heap to find minimum efficiently. Advance the pointer of minimum element and update range.

Algorithm

  1. Initialize pointers to first element of each list
  2. Build min-heap with (value, list index, element index)
  3. Track current maximum
  4. Range = [heap.min, currentMax]
  5. Pop minimum, advance its pointer, push next element
  6. Update maximum and range as needed
  7. Stop when any list is exhausted
java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        
        // Min-heap: {value, list index, element index}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]
        );
        
        int currentMax = Integer.MIN_VALUE;
        
        // Initialize with first element of each list
        for (int i = 0; i < k; i++) {
            int val = nums.get(i).get(0);
            minHeap.offer(new int[]{val, i, 0});
            currentMax = Math.max(currentMax, val);
        }
        
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;
        
        while (true) {
            // Get minimum element
            int[] curr = minHeap.poll();
            int minVal = curr[0];
            int listIdx = curr[1];
            int elemIdx = curr[2];
            
            // Update range if smaller
            if (currentMax - minVal < rangeEnd - rangeStart) {
                rangeStart = minVal;
                rangeEnd = currentMax;
            }
            
            // Move to next element
            if (elemIdx + 1 >= nums.get(listIdx).size()) {
                break;
            }
            
            int nextVal = nums.get(listIdx).get(elemIdx + 1);
            minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
            currentMax = Math.max(currentMax, nextVal);
        }
        
        return new int[]{rangeStart, rangeEnd};
    }
}

Complexity Analysis

  • Time Complexity: O(N*K log K) - Each element is pushed/popped once, heap has K elements
  • Space Complexity: O(K) - Heap stores K elements

Approach 3: Two Pointers with Sorting

Intuition

Similar to sliding window but with explicit tracking of which elements from each list are included.

Algorithm

  1. Merge all lists into sorted array with list indices
  2. Use two pointers to find minimum window containing all lists
  3. Track count of elements from each list in window
java
import java.util.*;

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        
        // Create merged sorted list
        List<int[]> merged = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            for (int num : nums.get(i)) {
                merged.add(new int[]{num, i});
            }
        }
        
        merged.sort((a, b) -> a[0] - b[0]);
        
        // Two pointers
        Map<Integer, Integer> listCount = new HashMap<>();
        int uniqueLists = 0;
        int left = 0;
        
        int minLen = Integer.MAX_VALUE;
        int rangeStart = 0, rangeEnd = 0;
        
        for (int right = 0; right < merged.size(); right++) {
            int listIdx = merged.get(right)[1];
            
            listCount.put(listIdx, listCount.getOrDefault(listIdx, 0) + 1);
            if (listCount.get(listIdx) == 1) {
                uniqueLists++;
            }
            
            // Shrink window
            while (uniqueLists == k) {
                int len = merged.get(right)[0] - merged.get(left)[0];
                
                if (len < minLen) {
                    minLen = len;
                    rangeStart = merged.get(left)[0];
                    rangeEnd = merged.get(right)[0];
                }
                
                int leftListIdx = merged.get(left)[1];
                listCount.put(leftListIdx, listCount.get(leftListIdx) - 1);
                if (listCount.get(leftListIdx) == 0) {
                    uniqueLists--;
                }
                left++;
            }
        }
        
        return new int[]{rangeStart, rangeEnd};
    }
}

Complexity Analysis

  • Time Complexity: O(NK log(NK)) - Sorting dominates
  • Space Complexity: O(N*K) - Storing merged array

Key Takeaways

  1. Min-Heap approach is space-optimal - O(K) space
  2. Heap maintains current element from each list efficiently
  3. Range is always [min of current elements, max of current elements]
  4. Stop when any list is exhausted (can't cover all lists anymore)
  5. This is LeetCode 632 - a classic heap problem
  6. Sliding window on merged array is also valid but uses more space
  7. Key insight: Advancing minimum element is the only way to potentially shrink range
  8. Similar to merge K sorted lists but with range tracking
Previous
Merge K Sorted Linked Lists [V.IMP]
Next
Median in a stream of Integers