Skip to content
Hello Python

Merge Sorted Rows

Practice ExerciseIntermediateMediumK-way MergeArrayHeap

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement merge_sorted_rows(rows). Every inner row is sorted ascending and may be empty. Return one ascending list containing all values and preserving duplicates.

Starter code

def merge_sorted_rows(rows):
    pass
Test cases

three-rows

{
  "args": [
    [
      [
        1,
        4,
        9
      ],
      [
        2,
        2,
        8
      ],
      [
        3,
        7
      ]
    ]
  ]
}

Expected: [1,2,2,3,4,7,8,9]

empty-rows

{
  "args": [
    [
      [],
      [
        1,
        5
      ],
      []
    ]
  ]
}

Expected: [1,5]

Wizard outline
  1. Step 1: Seed one source frontier

    Place the first item of every populated row into the heap. The global minimum must be among the current first unseen values.

  2. Step 2: Advance non-empty sources

    Push the next value from the row just popped. Sorted rows guarantee that every other unseen value in that row is no smaller than its new frontier; empty-source handling comes next.

  3. Step 3: Preserve duplicates and empty sources

    Complete the merge for repeated values and empty rows. Tuple identity keeps equal values from different positions as independent heap entries while an explicit seed guard skips empty sources.

Footguns and prerequisites
  • Pushing every value defeats the O(k) frontier-space advantage.
  • A heap entry without source and offset cannot advance the correct row.
  • arrays strings two pointers sliding window
Reviewed references
Recommended approach and implementation

Maintain one heap frontier per non-empty sorted row and advance only the row that supplies the minimum.

Why it works: The smallest unseen value must be at one row frontier, so each heap pop is the next global value. Replacing it with that row’s next value preserves the invariant until every row is exhausted.

import heapq

def merge_sorted_rows(rows):
    heap = []
    for row_index, row in enumerate(rows):
        if row:
            heapq.heappush(heap, (row[0], row_index, 0))
    merged = []
    while heap:
        value, row_index, element_index = heapq.heappop(heap)
        merged.append(value)
        next_index = element_index + 1
        if next_index < len(rows[row_index]):
            heapq.heappush(heap, (rows[row_index][next_index], row_index, next_index))
    return merged