The O(n) Club: Smallest Range from K Lists: Heapify or Cry in Brute Force

The O(n) Club: Smallest Range from K Lists—Heapify or Cry in Brute Force

⚡ TL;DR

If you want the smallest interval covering one number from each of k sorted lists, skip brute force unless you enjoy watching your code timeout. Use a min-heap, pointer-juggling, and just enough caffeine to power your brain, not the AWS bill.

// Java sketch (don't brute force this!)
// O(n^k) means you meet the heat death of the universe first.
 // Smart: Min-heap gets the smallest, keep track of biggest. Advance pointers smartly.

🧠 How Devs Usually Mess This Up

Nothing like a haunted for-loop through every combo: O(n^k) ways to cook your CPU. Or maybe you thought you had to cover all values, not just one from each list. Bonus: Forgetting to break ties using the smaller starting value—because who cares about problem statements, right?

🔍 What’s Actually Going On

This is like organizing a multi-cuisine buffet for picky eaters: everyone wants the smallest plate containing at least one dish from each cuisine. You’re not sliding cutters over every dish. You’re using a robot arm (min-heap) to always serve the smallest dish on your custom plate, while also peeking at the spiciest outlier. You keep swapping in the next from whichever cuisine just ran out, until someone’s kitchen closes shop. Fast, satisfying, zero waiters harmed.

🛠️ PseudoCode

• Start: Add the first number from each list to a min-heap. Record the biggest of these (max-so-far).
• Loop while the heap’s full (one from each list):
  • Pop min (heap’s smallest number) with its list and index.
  • If [min, current max] is the best (tightest) range yet, save it.
  • Push the next number from min’s list, if it exists; also, update current max if that new value’s bigger.
  • If you run off the end of any list, stop—your buffet’s officially out of food.

// Java-flavored pseudocode
Class Node(val, listIdx, eleIdx)
heap = new PriorityQueue<Node> by val
maxValue = -∞
for (list i in lists)
    heap.add(Node(lists[i][0], i, 0))
    maxValue = max(maxValue, lists[i][0])
range = [heap.peek().val, maxValue]
while (heap.size == k):
    node = heap.poll()
    update range if tighter
    if node.eleIdx + 1 == lists[node.listIdx].length: break
    nextVal = lists[node.listIdx][node.eleIdx+1]
    heap.add(Node(nextVal, node.listIdx, node.eleIdx+1))
    maxValue = max(maxValue, nextVal)

💻 The Code

import java.util.*;
 class Solution {
    static class Node {
        int val, listIdx, eleIdx;
        Node(int val, int listIdx, int eleIdx) {
            this.val = val;
            this.listIdx = listIdx;
            this.eleIdx = eleIdx;
        }
    }
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            pq.add(new Node(v, i, 0));
            max = Math.max(max, v);
        }
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;
        while (pq.size() == nums.size()) {
            Node n = pq.poll();
            if (max - n.val < rangeEnd - rangeStart || (max - n.val == rangeEnd - rangeStart && n.val < rangeStart)) {
                rangeStart = n.val;
                rangeEnd = max;
            }
            int ni = n.eleIdx + 1;
            if (ni < nums.get(n.listIdx).size()) {
                int nextVal = nums.get(n.listIdx).get(ni);
                pq.add(new Node(nextVal, n.listIdx, ni));
                if (nextVal > max) max = nextVal;
            } else {
                break;
            }
        }
        return new int[]{rangeStart, rangeEnd};
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Heaps are not charity: Always keep exactly one value per list; if you break this, you leave a cuisine out. Not cool.
• Empty lists? Return an error. There’s no smallest range in zero dimensions.
• Off-by-one disasters: Don’t move past the end. Java will only forgive you so many NullPointers.
• Time/Space: O(N log K) time, O(K) heap. You’ll look smart and your machine won’t sweat.

🧠 Interviewer Brain-Tattoo

“Why cook up every combo when you can serve the perfect range in O(N log K)? Let the heap do the heavy lifting—your brain has bigger interviews to ace.”