Example 1
ready- Input
lists = [ [ 1, 4, 5 ], [ 1, 3, 4 ], [ 2, 6 ] ]- Expected
[ 1, 1, 2, 3, 4, 4, 5, 6 ]- Why
- the three sorted streams interleave into one ordered result
Merge K Sorted Lists
50 min · mergeKLists()Several sorted result feeds arrive at once. You need one clean timeline, and rereading all the values after every choice won't survive the largest import.
Given lists, an array of integer arrays, merge every value into one sorted array and
return it. Each inner array is already sorted in non-decreasing order.
Non-decreasing means each value is at least the value before it, so duplicates are allowed.
A few ground rules:
- An inner array may be empty, and
listsitself may be empty. - Keep every occurrence of every value, including duplicates across different arrays.
- The returned array must be sorted in non-decreasing order.
Constraints
0 <= lists.length <= 10_0000 <= lists[i].length- The total number of values across all inner arrays is at most
100_000. - Every
lists[i]is sorted in non-decreasing order. -1_000_000_000 <= lists[i][j] <= 1_000_000_000
Hints
Start with the honest baseline
You can collect every value and sort the result. That works, but it throws away the ordering each input array already gives you.
Only k values are ready
At any moment, the next answer must be one of the current first unused values from the non-empty arrays. How could you retrieve the smallest of those candidates?
Remember where a value came from
Put each current head in a min-heap along with its array index and position. After removing one, advance only that array and add its next value.
Follow-up
Can you explain why the heap never needs more than one entry per input array, even when the arrays together contain 100,000 values?
Visible cases
Examples
Example 2
ready- Input
lists = []- Expected
[]- Why
- no input arrays means no values to merge
Example 3
ready- Input
lists = [ [] ]- Expected
[]- Why
- an empty inner array contributes nothing
Interview signal
Asked at
AmazonGoogleMicrosoftUber
Concatenate + sort
The direct route is reliable: copy every value into one array, then sort that array.
def merge_k_lists(lists: list[list[int]]) -> list[int]:
merged: list[int] = []
for values in lists:
merged.extend(values)
merged.sort()
return mergedThis answer ignores a valuable promise. Every input array is already sorted, yet the final sort treats all N values as if they arrived in random order.
Time O(N log N), where N is the total number of values. Space O(N) for the returned array.
K-head min-heap
A min-heap is a structure that removes its smallest stored item efficiently. Add the first value from every non-empty array. The heap now contains every value that could possibly come next.
When you remove (value, list_index, element_index), append value to the answer. Then
advance only that source array: if it has another value, add that next entry to the heap.
import heapq
def merge_k_lists(lists: list[list[int]]) -> list[int]:
heap: list[tuple[int, int, int]] = []
for list_index, values in enumerate(lists):
if values:
heapq.heappush(heap, (values[0], list_index, 0))
merged: list[int] = []
while heap:
value, list_index, element_index = heapq.heappop(heap)
merged.append(value)
next_index = element_index + 1
if next_index < len(lists[list_index]):
next_value = lists[list_index][next_index]
heapq.heappush(heap, (next_value, list_index, next_index))
return mergedThe heap holds at most one current head from each of the k arrays. Each of the N values enters and leaves it once.
Time O(N log k). Space O(k) beyond the returned array.
LeetCode's version receives and returns linked lists; ours uses plain arrays as the wire form of those same lists.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 1, 1, 2, 3, 4, 4, 5, 6 ]
Run: visible + custom · Submit: full suite