{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Merge K Sorted Lists – Solution & Complexity

Interview solutions
/
Merge K Sorted Lists

Solution Walkthrough

  1. Step 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. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)K Closest Points to Origin solution (medium)Kth Largest Element in an Array solution (medium)Sort List solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?