{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Merge K Sorted Lists – Solution & Complexity

Interview solutions
/
Merge K Sorted Lists

1. Recognize the Pattern

The key pattern is: A min-heap retains one current value from each list. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n log k). Space: O(k).

def merge_k_lists(lists: list[list[int]]) -> list[int]:
    import heapq
    heap = [(values[0], i, 0) for i, values in enumerate(lists) if values]
    heapq.heapify(heap)
    answer = []
    while heap:
        value, list_index, index = heapq.heappop(heap)
        answer.append(value)
        if index + 1 < len(lists[list_index]):
            heapq.heappush(heap, (lists[list_index][index + 1], list_index, index + 1))
    return answer

FAQ

See also

Practice Merge K Sorted Lists online (run code in the browser)Find Median from Data Stream solution (hard)Kth Largest Element in an Array solution (medium)Top K Frequent Elements solution (medium)Linked List Cycle solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?