Merge K Sorted Lists Using Min Heap in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging 3 sorted lists using a min heap

What is the printed output of the merged linked list after running this code?

DSA Python

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    min_heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(min_heap, (node.val, i, node))
    dummy = ListNode(0)
    current = dummy
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
    return dummy.next

# Lists:
# 1 -> 4 -> 5
# 1 -> 3 -> 4
# 2 -> 6

l1 = ListNode(1, ListNode(4, ListNode(5)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
l3 = ListNode(2, ListNode(6))

merged = merge_k_lists([l1, l2, l3])

# Print merged list
result = []
while merged:
    result.append(merged.val)
    merged = merged.next
print(result)

A [1, 1, 3, 4, 4, 5, 6]

B [1, 2, 3, 4, 4, 5, 6]

C [1, 1, 2, 3, 4, 5, 6]

D [1, 1, 2, 3, 4, 4, 5, 6]

💡 Hint

Think about how the min heap always picks the smallest current node from all lists.

The min heap merges nodes by always choosing the smallest value among the heads of the lists. The merged list contains all elements in sorted order.

🧠 Conceptual

intermediate

Why use a min heap to merge K sorted lists?

What is the main advantage of using a min heap to merge K sorted linked lists?

A It merges lists by concatenating them without sorting.

B It allows efficient retrieval of the smallest current element among all lists in O(log K) time.

C It sorts each individual list before merging.

D It uses extra memory to store all elements at once for sorting.

💡 Hint

Think about how to efficiently find the smallest element among multiple sorted lists.

A min heap keeps track of the smallest elements from each list, allowing efficient extraction and insertion in O(log K) time, where K is the number of lists.

❓ Predict Output

advanced

Output of merging empty and non-empty lists

What is the output of merging these lists using the min heap approach?

DSA Python

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    min_heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(min_heap, (node.val, i, node))
    dummy = ListNode(0)
    current = dummy
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
    return dummy.next

l1 = None
l2 = ListNode(0)
l3 = None

merged = merge_k_lists([l1, l2, l3])

result = []
while merged:
    result.append(merged.val)
    merged = merged.next
print(result)

A [0]

B []

C [None]

D [0, None]

💡 Hint

Consider how the function handles empty lists and single-node lists.

Only the second list has one node with value 0. The merged list contains just that value.

🔧 Debug

advanced

Identify the error in this min heap merge implementation

What error will this code raise when merging K sorted lists using a min heap?

DSA Python

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    min_heap = []
    for node in lists:
        if node:
            heapq.heappush(min_heap, (node.val, node))
    dummy = ListNode(0)
    current = dummy
    while min_heap:
        val, node = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        if node.next:
            heapq.heappush(min_heap, (node.next.val, node.next))
    return dummy.next

l1 = ListNode(1, ListNode(3))
l2 = ListNode(1)
merged = merge_k_lists([l1, l2])

A TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'

B AttributeError: 'NoneType' object has no attribute 'val'

C IndexError: list index out of range

D No error, runs successfully

💡 Hint

Consider what happens when two nodes have the same value in the heap.

When two nodes have the same value, the heap tries to compare ListNode objects which is not supported, causing a TypeError.

🚀 Application

expert

Time complexity of merging K sorted lists with N total elements using a min heap

What is the time complexity of merging K sorted linked lists with a total of N elements using a min heap?

A O(N K)

B O(K log N)

C O(N log K)

D O(N + K log N)

💡 Hint

Consider how many times elements are pushed and popped from the heap and the heap size.

Each of the N elements is pushed and popped once from a heap of size at most K, so the complexity is O(N log K).

Practice

1. What is the main advantage of using a min heap to merge k sorted lists?

easy

A. It efficiently finds the smallest element among the heads of all lists.

B. It sorts each individual list before merging.

C. It uses extra space to store all elements at once.

D. It merges lists by concatenating them directly.

Solution

1. Step 1: Understand the role of min heap in merging

   A min heap helps keep track of the smallest element among multiple sorted lists efficiently.

2. Step 2: Compare with other options

   Options B, C, and D do not describe the min heap's main advantage in this context.

3. Final Answer:

   It efficiently finds the smallest element among the heads of all lists. -> Option A

4. Quick Check:

   Min heap = smallest element tracking [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap sorts entire lists
• Assuming min heap stores all elements at once
• Confusing concatenation with merging

2. Which of the following Python code snippets correctly initializes a min heap with the first elements of each sorted list named lists?

easy

A. heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap)

B. heap = lists[0]; import heapq; heapq.heapify(heap)

C. heap = []; for lst in lists: heap.append(lst); import heapq; heapq.heapify(heap)

D. heap = lists; import heapq; heapq.heapify(heap)

Solution

1. Step 1: Extract first elements safely

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) uses list comprehension to get first elements only if the list is not empty.

2. Step 2: Check heap initialization

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) then calls heapq.heapify to create a min heap from these elements correctly.

3. Final Answer:

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) -> Option A

4. Quick Check:

   Correct min heap initialization = heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) [OK]

Hint: Use list comprehension with condition and heapq.heapify [OK]

Common Mistakes:

• Not checking if list is empty before accessing lst[0]
• Heapifying entire lists instead of first elements
• Assigning heap to a single list instead of elements

3. What will be the output of the following code snippet that merges 3 sorted lists using a min heap?

import heapq
lists = [[1,4,5],[1,3,4],[2,6]]
heap = []
for i, lst in enumerate(lists):
    if lst:
        heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
    val, list_idx, element_idx = heapq.heappop(heap)
    result.append(val)
    if element_idx + 1 < len(lists[list_idx]):
        next_tuple = (lists[list_idx][element_idx+1], list_idx, element_idx+1)
        heapq.heappush(heap, next_tuple)
print(result)

medium

A. [1, 2, 3, 4, 5, 6]

B. [1, 1, 2, 3, 4, 5, 6, 7]

C. [1, 1, 3, 4, 4, 5, 6]

D. [1, 1, 2, 3, 4, 4, 5, 6]

Solution

1. Step 1: Trace heap operations

   Initially, heap contains (1,0,0), (1,1,0), (2,2,0). We pop smallest 1, add next element 4 from list 0, then pop next 1, add 3 from list 1, and so on.

2. Step 2: Build merged list step-by-step

   Result builds as [1,1,2,3,4,4,5,6] by always popping smallest and pushing next from same list.

3. Final Answer:

   [1, 1, 2, 3, 4, 4, 5, 6] -> Option D

4. Quick Check:

   Merged sorted list = [1,1,2,3,4,4,5,6] [OK]

Hint: Track heap pops and pushes carefully [OK]

Common Mistakes:

• Missing duplicate 1s in output
• Forgetting to push next element from same list
• Adding elements out of order

4. Identify the error in the following code snippet that attempts to merge k sorted lists using a min heap:

import heapq
lists = [[1,3,5],[2,4,6],[0,7,8]]
heap = []
for lst in lists:
    heapq.heappush(heap, lst[0])
result = []
while heap:
    val = heapq.heappop(heap)
    result.append(val)
print(result)

medium

A. The lists variable is not defined.

B. The heap is not initialized using heapq.heapify().

C. The code pushes only first elements and never pushes next elements from lists.

D. The code uses heappop instead of pop.

Solution

1. Step 1: Analyze heap push operations

   The code pushes only the first element of each list into the heap once and never pushes subsequent elements.

2. Step 2: Understand why this causes incomplete merge

   Without pushing next elements, only first elements are merged, so the result is incomplete and incorrect.

3. Final Answer:

   The code pushes only first elements and never pushes next elements from lists. -> Option C

4. Quick Check:

   Missing next elements push = The code pushes only first elements and never pushes next elements from lists. [OK]

Hint: Always push next elements after popping from heap [OK]

Common Mistakes:

• Assuming heapq.heapify is mandatory here
• Confusing heappop with pop
• Ignoring the need to push next elements

5. Given k sorted linked lists, which approach best describes how to merge them efficiently using a min heap? A) Insert all nodes from all lists into a min heap, then pop all to form merged list. B) Push only the first node of each list into the min heap, then repeatedly pop the smallest node and push its next node until all nodes are merged. C) Merge lists two at a time using simple merge, then merge results. D) Concatenate all lists and sort the combined list.

hard

A. Insert all nodes at once into min heap and pop all.

B. Push first nodes, pop smallest, push next nodes repeatedly.

C. Merge lists two at a time without heap.

D. Concatenate all lists and sort at the end.

Solution

1. Step 1: Understand efficient min heap usage

   Pushing only the first node of each list keeps the heap small and efficient.

2. Step 2: Describe the merging process

   Pop smallest node, add it to merged list, then push the next node from that list to heap, repeating until done.

3. Step 3: Compare with other options

   Insert all nodes at once into min heap and pop all. wastes space and time by pushing all nodes at once. Options B and D do not use min heap.

4. Final Answer:

   Push first nodes, pop smallest, push next nodes repeatedly. -> Option B

5. Quick Check:

   Efficient merge = push first nodes, pop smallest, push next [OK]

Hint: Push first nodes only, then push next after popping [OK]

Common Mistakes:

• Pushing all nodes at once wastes memory
• Not pushing next nodes after popping
• Using simple merge instead of heap for k lists