Merge k Sorted Lists

Q: What is the time complexity of Merge k Sorted Lists?

With a min-heap it is O(N log k) , where N is the total number of values and k the number of lists. Each value is pushed and popped once, and the heap holds at most k entries. The extra memory is O(k) besides the output.

Q: Why not put all the values together and sort them?

That is correct and takes O(N log N) time. It ignores that the lists are already sorted, so it pays log N per value where the heap pays log k , and it needs every value in memory at once. The heap can also merge lists that arrive as streams.

HardHeap Linked list

+10

You get k lists of integers as the rows of lists. Each row is sorted in non-decreasing order, rows can have different lengths, and no row is empty.

Merge them into one list that holds every value from every row, sorted in non-decreasing order, and return it. A value that appears several times, in one row or in several, appears that many times in the result.

Function

mergeKLists(lists: integer-2d-array) → integer-array

listsinteger-2d-array: the sorted lists, one per row, of possibly different lengths
Returnsinteger-array: every value from every row, in one sorted list

Constraints

1 ≤ lists.length ≤ 10⁴
1 ≤ lists[i].length, and all rows together hold at most 10⁴ values
-10⁴ ≤ lists[i][j] ≤ 10⁴
Every row is sorted in non-decreasing order.

Examples

Input: lists = [[2, 6, 9], [1, 4, 10], [3, 5]]
Output: [1, 2, 3, 4, 5, 6, 9, 10]
Explanation: The rows start with 2, 1 and 3, so 1 comes first. The heads are then 2, 4 and 3, so 2 follows, and so on. The third row runs out after 5, leaving 6, 9 and 10.

Input: lists = [[5], [-2, 5, 7], [0, 5]]
Output: [-2, 0, 5, 5, 5, 7]
Explanation: The three 5s come from three different rows and all three stay. The negative -2 sorts before 0.

Follow-up

Find the smallest range [a, b] holding a value from every row. Can a heap of row heads plus the largest head do it in O(N log k)?

Solution

Each row is sorted, so the smallest unused value is always the first unused value of some row, its head. Scanning all k heads costs k steps for each of the N values. A min-heap of the heads hands out the smallest in O(log k), which brings the total from O(N·k) to O(N log k).

Compare all k heads for every value

Correct, but does not finish on the largest tests

Intuition

Keep an index pos[r] at the head of each row. Each round reads every head, appends the smallest and moves that row's index forward: the merge step of merge sort, widened from two lists to k. In the first example the heads start as 2, 1 and 3, so 1 goes out and the second row's head becomes 4.

Each of the N values costs a pass over all k rows. With 10^4 rows of one value each, that is 10^8 row checks.

Algorithm

Set pos[r] = 0 for every row and count the values, N.
Repeat N times: look at every row with pos[r] still inside it and remember the row whose head is the smallest.
Append that head to the result and add 1 to that row's pos.
Return the result.

def mergeKLists(lists):
    pos = [0] * len(lists)  # pos[r]: index of the first unused value in row r
    total = sum(len(row) for row in lists)
    merged = []
    for _ in range(total):
        best = -1  # the row whose head is the smallest so far
        for r in range(len(lists)):
            if pos[r] < len(lists[r]) and (best == -1 or lists[r][pos[r]] < lists[best][pos[best]]):
                best = r
        merged.append(lists[best][pos[best]])
        pos[best] += 1
    return merged

Min-heap of the k heads

Intuition

After each pick only one head changes, yet the scan rereads all k. A min-heap keeps the heads with the smallest on top. Tag each head with its row, so after popping (value, row) you know which row's next value to push. The heap always holds one entry per row with values left, so its top is the smallest unused value.

In the first example the heap starts with 2, 1 and 3. Pop 1, push 4. Pop 2, push 6. Pop 3, push 5. Pop 4, push 10. Pop 5: the third row is used up, so nothing goes in. Pop 6, push 9, then pop 9 and 10.

Each value enters and leaves once, and the heap never holds more than k entries: 2N operations of O(log k). With N = k = 10^4 that is under 3 × 10^5 steps. The heap takes O(k) memory.

Algorithm

Push (lists[r][0], r) for every row r into a min-heap ordered by value.
While the heap is not empty, pop the smallest pair (value, r) and append value to the result.
If row r has a next value, push it together with r.
Return the result once the heap is empty.

import heapq


def mergeKLists(lists):
    # The heap holds one (value, row) pair per row that still has values: that row's head.
    heap = [(row[0], r) for r, row in enumerate(lists)]
    heapq.heapify(heap)
    nxt = [1] * len(lists)  # nxt[r]: index of row r's next value, not yet in the heap
    merged = []
    while heap:
        value, r = heapq.heappop(heap)  # the smallest head of all rows
        merged.append(value)
        if nxt[r] < len(lists[r]):
            heapq.heappush(heap, (lists[r][nxt[r]], r))  # row r's new head takes its place
            nxt[r] += 1
    return merged

Pitfalls and edge cases

Pushing bare values. After a pop you cannot tell which row to advance. Store the row with the value.
Using a max-heap by mistake. C++ priority_queue and Rust BinaryHeap put the largest on top; use greater<> or Reverse.
Pushing every value at the start. The result is still sorted, but the heap grows to N entries and the work becomes O(N log N).
Reading past the end of a short row. In the first example the third row has two values, so check for a next value before pushing.
Dropping duplicates. The three 5s in the second example are separate values, and all of them belong in the result.

Frequently asked questions3

What is the time complexity of Merge k Sorted Lists?

With a min-heap it is O(N log k), where N is the total number of values and k the number of lists. Each value is pushed and popped once, and the heap holds at most k entries. The extra memory is O(k) besides the output.

Why not put all the values together and sort them?

That is correct and takes O(N log N) time. It ignores that the lists are already sorted, so it pays log N per value where the heap pays log k, and it needs every value in memory at once. The heap can also merge lists that arrive as streams.

Can you merge k sorted lists without a heap?

Yes, by divide and conquer. Merge the lists in pairs with the two-list merge, then merge the results in pairs, and so on: log k rounds that each touch every value once, so O(N log k). Merging the lists one after another into a growing result is slower, O(N·k), because early values are copied again in every merge.

def mergeKLists(lists):
    # Write code here

Test #1

Test #2

Test #3

Argument

lists = [[2, 6, 9], [1, 4, 10], [3, 5]]

Expected Output

[1, 2, 3, 4, 5, 6, 9, 10]