Day 63: Python Merge K Sorted Lists - O(n log k) Min-Heap Guide (LeetCode #23 Vibes)

Source: Dev.to

Welcome to Day 63 of the #80DaysOfChallenges journey! This intermediate challenge tackles the powerhouse Merge K Sorted Lists problem (LeetCode #23), where you fuse multiple sorted arrays into one master sorted list using a min‑heap for O(n log k) time—the optimal way to handle big‑data merges like combining sorted logs, search results, or database queries. The solution uses heapq to always grab the smallest next element from the k lists, with a tuple (value, list_index, elem_index) to track sources without losing position.

Key Takeaways from Day 63: Merge K Lists Function

1. Function Design: Heap Setup with Tuples

import heapq
from typing import List

def merge_k_sorted_lists(lists: List[List[int]]) -> List[int]:
    """
    Merge k sorted lists into a single sorted list.
    Uses a min‑heap to always extract the smallest available element.
    """
    heap: List[tuple[int, int, int]] = []   # (value, list_index, element_index)
    result: List[int] = []

    # initialize heap with first element of each list
    for i, lst in enumerate(lists):
        if lst:                     # skip empty lists
            heapq.heappush(heap, (lst[0], i, 0))

The heap starts with (value, list_i, elem_i) tuples; value is the priority for the min‑heap. Enumerating gives the list index, and 0 is the element position. Empty lists are ignored, keeping the heap size at k with each push costing O(log k).

2. Loop Processing: Pop Smallest, Push Next

    while heap:
        val, list_i, elem_i = heapq.heappop(heap)
        result.append(val)          # append smallest value to result

        next_i = elem_i + 1
        if next_i < len(lists[list_i]):
            next_val = lists[list_i][next_i]
            heapq.heappush(heap, (next_val, list_i, next_i))
            # push next element from same list

    return result

Each iteration pops the smallest value (O(log k)), appends it to result, and pushes the next element from the same list if one exists (O(log k)). The total complexity is O(n log k), where n is the total number of elements across all lists.

3. Main Interactive: Comma‑Separated List Parsing

raw = input("Enter sorted lists (comma-separated, space-separated numbers): ").strip()

lists = []
for part in raw.split(","):
    nums = list(map(int, part.strip().split()))
    lists.append(nums)

merged = merge_k_sorted_lists(lists)
print(f"Merged list: {merged}")

The script reads a line of input where individual lists are separated by commas and numbers within each list are space‑separated. It gracefully handles empty lists and produces the merged output.

Summary and Reflections

• Heap for multi‑merge: log k per element, far better than the naïve O(n k) approach.
• Tuple priority: The value comes first, followed by indices for tracking source lists.
• Skip empties: Makes the algorithm robust for real‑world data streams.

The technique mirrors core operations in Hadoop merges, database joins, and other large‑scale data processing tasks. For environments without heapq, a custom priority‑queue implementation can be used.

Next Steps and Resources

• Source Code for Challenge #63: scripts/merge_k_sorted_lists.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)