DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

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

#challenge #python #algorithms #datastructures

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. It uses heapq to always grab the smallest next element from k lists, with tuple (value, list_index, elem_index) to track sources without losing position. If you're leveling up to heap-based algorithms, preparing for interviews where "merge k lists" is a staple, or dealing with multi-stream data, this "Python merge k sorted lists" script is efficient, scalable, and the exact min-heap technique that crushes real-world merging tasks.

💡 Key Takeaways from Day 63: Merge K Lists Function

This task features a function that initializes a heap with first elements from each list, then pops and pushes nexts until empty, building the merged list. It's a priority queue pattern: heap ensures smallest always first. We'll detail: function with heap initialization, loop for pop and push, and main with comma-separated input.

1. Function Design: Heap Setup with Tuples

The merge_k_sorted_lists function takes list of lists, returns merged:

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 = []                       # min-heap to track next smallest elements
    result = []                     # final merged output

    # 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))
            # (value, list_index, element_index)
Enter fullscreen mode Exit fullscreen mode

Heap starts with (val, list_i, elem_i) tuples, val as priority for min-heap. Enumerate gives list index, 0 for element position. Skips empties. Heap size k, push O(log k).

2. Loop Processing: Pop Smallest, Push Next

Core while extracts:

    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
Enter fullscreen mode Exit fullscreen mode

Pops smallest val (O(log k)), appends to result. Pushes next from same list if exists (O(log k)). Total O(n log k), n total elements. Handles varying lengths.

3. Main Interactive: Comma-Separated List Parsing

Script reads multi-lists:

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}")
Enter fullscreen mode Exit fullscreen mode

Splits by comma for lists, space for nums. Flexible, handles empties.

🎯 Summary and Reflections

This merge k lists uses heap for multi-pointer efficiency without manual min-finding. It reinforced:

  • Heap for multi-merge: Log k per element, beats O(nk).
  • Tuple priority: Val first, indices for tracking.
  • Skip empties: Robust for real data.

Reflections: Core to Hadoop merges, database joins. For no heap, use priority queue lib.

Advanced Alternatives: Binary heap with custom class. Merge sort trees for ranges. Your merge tip? Share!

🚀 Next Steps and Resources

Day 63 fused data like a boss. In #80DaysOfChallenges? Merged huge? Post!

Top comments (0)