LeetCode 23 Merge K Sorted Lists - Example and Complexity Analysis

Trace [[1,4,5], [1,3,4], [2,6]] with a min-heap.

Initialize heap with heads: [1, 1, 2] (from lists 0, 1, 2).

Pop 1 (list 0). Result: 1. Push 4. Heap: [1, 2, 4].

Pop 1 (list 1). Result: 1 → 1. Push 3. Heap: [2, 3, 4].

Pop 2 (list 2). Result: 1 → 1 → 2. Push 6. Heap: [3, 4, 6].

Continue until heap is empty: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6.

Each of $n$ nodes is pushed and popped once. Each heap operation is $O(\log k)$. Total: $O(n \log k)$ time.

Heap stores at most $k$ elements. $O(k)$ space.