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, so each operation costs O(log k) . 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, which is fine for small inputs. It ignores the fact 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, which sorting cannot.

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 smallest value overall is 1, the first value of the second row. After it the rows start with 2, 4 and 3, so 2 is next, and so on. The third row runs out after 5, which leaves 6, 9 and 10 at the end.

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.

+14 hidden tests on Submit

Follow-up

Find the smallest range [a, b] that holds at least one value from every row. Can the same heap of row heads, plus the largest head so far, find it in O(N log k)?

Solution

Every row is sorted, so the smallest value nobody has used yet is always the first unused value of some row. The whole problem is to find the smallest of k row heads, N times over, where N is the number of values. Scanning all the heads costs k steps per value. A min-heap keeps the heads ordered and hands out the smallest in O(log k), which takes the total from O(N·k) to O(N log k). In the classic form each list is a linked list; here each row is an array, and an index per row does the job of the node pointer.

Compare all k heads for every value

Correct, but does not finish on the largest tests

Intuition

Keep one index per row, pos[r], pointing at the first value of row r you have not used yet: the row's head. The smallest unused value of all must be one of these heads. Inside row r, every unused value sits at or after pos[r], and the row is sorted, so none of them is smaller than the head.

So find the smallest head by looking at every row that still has values, append it, and move that row's index one step forward. Repeat until all N values are out. This is the merge step of merge sort, widened from two lists to k.

On the first example the heads start as 2, 1 and 3, so 1 goes out first and the second row's head becomes 4. Then 2 (heads 2, 4, 3), then 3 (heads 6, 4, 3), then 4, then 5, which empties the third row. The last three rounds compare only 6 and 10, then 9 and 10, then 10 alone.

The cost is k comparisons for each of the N values. With 10^4 rows of one value each, that is 10^8 comparisons. C, Java or JavaScript get through them in under a second, but Python needs over ten seconds, and doubling both N and k makes every language four times slower. The waste shows in the trace: after each pick only one head has changed, yet the next round reads all k again.

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

The scan rereads k heads to find the smallest, although only one head changed since the last round. A min-heap is made for exactly this: it holds a set of numbers with the smallest on top, and both taking the top and adding a number cost O(log size).

Put the first value of every row in the heap, each tagged with its row number. Then repeat: pop the smallest pair (value, row), append value, and if that row has another value, push it with the same tag. The heap always holds exactly one entry for each row that still has values, its head, so the top is the smallest unused value overall. It is the scan's rule, answered faster.

Trace the first example with rows numbered from 0. The heap starts with 2 (row 0), 1 (row 1) and 3 (row 2). Pop 1 and push row 1's next value, 4. Pop 2 and push 6 from row 0. Pop 3 and push 5 from row 2. Pop 4 and push 10. Pop 5: row 2 is used up, so nothing goes in and the heap shrinks to 6 and 10. Pop 6 and push 9. Pop 9, then 10. The result is [1, 2, 3, 4, 5, 6, 9, 10].

Every value enters the heap once and leaves once, and the heap never holds more than k entries, so each of those 2N operations costs O(log k). With N = k = 10^4 that is about 2 × 10^4 × 14, under 3 × 10^5 steps, against 10^8 for the scan. The heap uses O(k) memory, never O(N), because it keeps one head per row and not the values behind it.

Several versions build the heap by hand, in an array of row numbers ordered by each row's head, with the children of slot i at 2i+1 and 2i+2 (at 2i and 2i+1 in Lua and R, which count from 1). It also saves work: after taking the top row's head, the row's next value is no smaller, so the row stays at the top and sifts down once, instead of a pop followed by a push.

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

The heap logic is short. Most bugs come from what goes into the heap and which way it is ordered.

Forgetting where a value came from. If the heap holds bare values, you cannot tell which row to advance after a pop. 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. Java's PriorityQueue and Python's heapq already give the smallest.
Ties in Python's heapq. When two values are equal, the tuple comparison moves on to the second item. A row number compares fine, but a linked-list node does not, and the classic version crashes on equal values. Put a row number or a counter second.
Pushing every value at the start. It still sorts correctly, but the heap grows to N entries and the work becomes O(N log N). Keep one head per row.
Reading past the end of a short row. Rows have different lengths, so check that a row has a next value before pushing it.
Dropping duplicates. Equal values from different rows are separate values, and all of them belong in the result.

Frequently asked questions4

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, so each operation costs O(log k). 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, which is fine for small inputs. It ignores the fact 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, which sorting cannot.

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. There are log k rounds and each round touches every value once, so it is also O(N log k). Merging the lists one after another into a growing result is slower: the early values are copied again in every merge, which adds up to O(N·k).

Why does the heap only need the head of each list?

Each list is sorted, so its first unused value is the smallest value it has left. The smallest value among all lists is therefore the smallest of their heads, and no value deeper in a list can beat it. When a head leaves, the next value of the same list becomes that list's head and takes its place in the heap.

Python

def mergeKLists(lists):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected

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