Merge K Sorted Lists

▶

Steps

setup

Initialize lists array

We start with the input array of three sorted linked lists: [1->4->5], [1->3->4], and [2->6]. This array is the starting point for merging.

💡 Initializing the array of lists is essential because the algorithm merges these lists pairwise until one remains.

Line:

lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]

💡 The problem reduces to merging these multiple sorted lists into one sorted list.

expand

Start first merge interval = 1

Set interval to 1 to merge lists in pairs: merge lists[0] with lists[1], then lists[2] remains alone.

💡 Interval controls the size of pairs to merge; starting with 1 means merging adjacent pairs.

Line:

interval = 1
while interval < len(lists):

💡 The algorithm merges pairs of lists at increasing intervals to reduce the number of lists.

merge

Merge lists[0] and lists[1] - start

Begin merging the first two lists: [1->4->5] and [1->3->4]. Compare their head nodes to pick the smaller value.

💡 Merging two lists is the core operation; comparing head nodes decides which node to add next.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 The smallest head node between the two lists is chosen to maintain sorted order.

compare

Compare heads: 1 vs 1, pick second list's node

Both lists have head value 1. The algorithm picks the node from the second list (lists[1]) and advances its pointer.

💡 When values are equal, the algorithm consistently picks from the second list to maintain stability.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next
else:
    current.next = l2
    l2 = l2.next

💡 The else branch is taken when values are equal or l2 is smaller, ensuring correct order.

traverse

Advance pointers in mergeTwoLists

Advance the pointer in the second list (lists[1]) to its next node (3), preparing for the next comparison.

💡 Advancing pointers moves through the lists, progressively building the merged list.

Line:

l2 = l2.next

💡 Pointer movement is essential to traverse and merge all nodes.

compare

Compare heads: 1 vs 3, pick first list's node

Now comparing 1 (lists[0]) and 3 (lists[1]), the smaller value 1 from lists[0] is chosen and its pointer advances.

💡 Choosing the smaller head node keeps the merged list sorted.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The algorithm always picks the smaller node to maintain order.

traverse

Advance pointer in first list after picking 1

Advance the pointer in the first list (lists[0]) to its next node (4) for the next comparison.

💡 Moving pointers forward is how the algorithm progresses through the lists.

Line:

l1 = l1.next

💡 Pointer advancement is key to eventually exhausting both lists.

compare

Compare heads: 4 vs 3, pick second list's node

Comparing 4 (lists[0]) and 3 (lists[1]), the smaller 3 from lists[1] is chosen and its pointer advances.

💡 The algorithm picks the smaller node to maintain sorted order in the merged list.

Line:

else:
    current.next = l2
    l2 = l2.next

💡 Choosing the smaller node from either list keeps the merged list sorted.

traverse

Advance pointer in second list after picking 3

Advance the pointer in the second list (lists[1]) to its next node (4) for the next comparison.

💡 Advancing pointers moves the merge process forward.

Line:

l2 = l2.next

💡 Each pointer movement brings the merge closer to completion.

insert

Merge remaining nodes and update lists array

Finish merging lists[0] and lists[1] into one sorted list: 1->1->3->4->4->5. Update lists[0] with this merged list.

💡 Replacing the pair with the merged list reduces the number of lists to merge.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 Merging pairs reduces problem size, moving towards the final merged list.

expand

Double interval to 2 and prepare next merge

Increase interval to 2 to merge lists[0] and lists[2] (if exists). Now only two lists remain: merged list and [2->6].

💡 Increasing interval merges larger pairs, eventually merging all lists into one.

Line:

interval *= 2

💡 Doubling interval controls the merge granularity.

merge

Merge lists[0] and lists[1] (merged list and [2->6]) - start

Begin merging the merged list [1->1->3->4->4->5] with [2->6]. Compare their head nodes to pick the smaller value.

💡 Final merge combines the two remaining lists into the fully sorted list.

Line:

lists[i] = mergeTwoLists(lists[i], lists[i + interval])

💡 The final merge produces the complete sorted list.

compare

Compare heads: 1 vs 2, pick first list's node

Comparing 1 (merged list) and 2 ([2->6]), pick 1 from merged list and advance its pointer.

💡 Picking the smaller node keeps the merged list sorted.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The algorithm continues to pick the smallest node at each step.

traverse

Advance pointer in merged list after picking 1

Advance pointer in merged list to next node (1) for next comparison.

💡 Pointer movement is how the merge progresses through nodes.

Line:

l1 = l1.next

💡 Each advancement brings the merge closer to completion.

compare

Compare heads: 1 vs 2, pick first list's node again

Compare 1 (merged list) and 2 ([2->6]), pick 1 from merged list and advance pointer.

💡 Continuing to pick the smaller node maintains order.

Line:

if l1.val < l2.val:
    current.next = l1
    l1 = l1.next

💡 The merge continues smoothly picking smallest nodes.

traverse

Advance pointer in merged list after picking 1

Advance pointer in merged list to next node (3) for next comparison.

💡 Pointer movement is essential to progress.

Line:

l1 = l1.next

💡 Advancing pointers moves the merge forward.

compare

Compare heads: 3 vs 2, pick second list's node

Compare 3 (merged list) and 2 ([2->6]), pick 2 from second list and advance pointer.

💡 Picking the smaller node from either list keeps order.

Line:

else:
    current.next = l2
    l2 = l2.next

💡 The algorithm correctly picks the smaller node from the second list.

traverse

Advance pointer in second list after picking 2

Advance pointer in second list to next node (6) for next comparison.

💡 Pointer movement is how the merge progresses.

Line:

l2 = l2.next

💡 Advancing pointers moves the merge closer to completion.

insert

Finish merging and update lists array

Finish merging all nodes into one sorted list: 1->1->2->3->4->4->5->6. Update lists[0] with this final merged list.

💡 The final merged list is the answer to the problem.

Line:

return lists[0]

💡 The algorithm successfully merges all lists into one sorted list.

from typing import List, Optional

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

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)  # STEP 3
    current = dummy
    while l1 and l2:  # STEP 4-18
        if l1.val < l2.val:  # STEP 6, 13, 15
            current.next = l1
            l1 = l1.next  # STEP 7, 14, 16
        else:
            current.next = l2
            l2 = l2.next  # STEP 5, 9, 18
        current = current.next
    current.next = l1 if l1 else l2  # STEP 10, 19
    return dummy.next

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:  # STEP 1
        return None
    interval = 1  # STEP 2
    while interval < len(lists):  # STEP 2
        for i in range(0, len(lists) - interval, interval * 2):  # STEP 3
            lists[i] = mergeTwoLists(lists[i], lists[i + interval])  # STEP 3-19
        interval *= 2  # STEP 11
    return lists[0]  # STEP 19

if __name__ == '__main__':
    def create_list(arr):
        dummy = ListNode(0)
        cur = dummy
        for v in arr:
            cur.next = ListNode(v)
            cur = cur.next
        return dummy.next

    lists = [create_list([1,4,5]), create_list([1,3,4]), create_list([2,6])]  # STEP 1
    merged = mergeKLists(lists)  # STEP 2-19
    while merged:
        print(merged.val, end='->' if merged.next else '')
        merged = merged.next

📊

Merge K Sorted Lists - Watch the Algorithm Execute, Step by Step

Watching each merge operation and how the lists are combined helps you understand the divide and conquer approach clearly, beyond just reading code.

setupmin-heap

1

0

1

1

2

2

expandmin-heap

1

0

1

1

2

2

mergemin-heap

1

0

1

1

2

2

comparemin-heap

1

0

1

1

2

2

traversemin-heap

1

0

3

1

2

2

comparemin-heap

4

0

3

1

2

2

traversemin-heap

4

0

3

1

2

2

comparemin-heap

4

0

4

1

2

2

traversemin-heap

4

0

4

1

2

2

insertmin-heap

1

0

2

1

expandmin-heap

1

0

2

1

mergemin-heap

1

0

2

1

comparemin-heap

1

0

2

1

traversemin-heap

1

0

2

1

comparemin-heap

3

0

2

1

traversemin-heap

3

0

2

1

comparemin-heap

3

0

6

1

traversemin-heap

3

0

6

1

insertmin-heap

1

0

Added: "1->1->2->3->4->4->5->6"

Key Takeaways

✓ The divide and conquer approach merges pairs of lists repeatedly, reducing the problem size exponentially.

This insight is hard to see from code alone because the interval doubling and pairwise merges are subtle.

✓ Merging two sorted lists by comparing head nodes ensures the merged list remains sorted at every step.

Visualizing each comparison and pointer movement clarifies how the merge maintains order.

✓ Pointer advancement in each list is crucial to progress through the lists and complete the merge.

Watching pointer moves step-by-step reveals the mechanics behind the merge, which code alone can obscure.

Practice

1. Consider the following Python code that merges k sorted arrays using divide and conquer. Given the input arrays [[1,4,5],[1,3,4],[2,6]], what is the value of merged_arrays after the first iteration of the while loop inside merge_k_sorted_arrays?

easy

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

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

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

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

Solution

1. Step 1: Trace merging pairs in first iteration

   Arrays are [[1,4,5],[1,3,4],[2,6]]. Merge first two: merge_two_arrays([1,4,5],[1,3,4]) -> [1,1,3,4,4,5]. The last array [2,6] remains as is because no pair.

2. Step 2: Form merged_arrays after first iteration

   merged_arrays = [[1,1,3,4,4,5],[2,6]]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First pair merged correctly, last array unchanged -> matches [[1,1,3,4,4,5],[2,6]] [OK]

Hint: Merge pairs left to right, last array unchanged if odd count [OK]

Common Mistakes:

• Merging last array incorrectly
• Off-by-one in loop
• Appending arrays instead of merging

2. You have an array where each element is at most k positions away from its sorted position. Which algorithmic approach guarantees the most efficient sorting in terms of time complexity?

easy

A. Use a standard full sort like quicksort or mergesort on the entire array.

B. Use a min-heap of size k+1 to iteratively extract the smallest element and build the sorted array.

C. Apply a greedy approach by swapping elements only when they are out of order by more than k positions.

D. Use dynamic programming to find the minimum number of swaps needed to sort the array.

Solution

1. Step 1: Understand the problem constraints

   The array is almost sorted, with each element at most k positions away from its correct position.

2. Step 2: Identify the optimal approach

   A min-heap of size k+1 efficiently keeps track of the next smallest element within the window of possible positions, allowing sorting in O(n log k) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap size k+1 matches the maximum displacement constraint [OK]

Hint: Min-heap size k+1 exploits limited disorder [OK]

Common Mistakes:

• Assuming full sort is always best
• Trying greedy swaps without heap
• Using DP which is unnecessary here

3. Given the following Python code to find the nth ugly number, what is the output when nthUglyNumber(4) is called?

easy

A. 6

B. 5

C. 8

D. 4

Solution

1. Step 1: Trace heap pops and pushes for n=4

   Initial heap: [1]. Iteration 1 pops 1, pushes 2,3,5. Iteration 2 pops 2, pushes 4,6,10. Iteration 3 pops 3, pushes 6,9,15 (6 already in seen, skip). Iteration 4 pops 4, pushes 8,12,20.

2. Step 2: Identify the 4th popped ugly number

   The popped numbers in order are 1,2,3,4. The 4th ugly number popped is 4, so the output is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   4 is the 4th ugly number [OK]

Hint: Trace heap pops carefully to find nth ugly number [OK]

Common Mistakes:

• Off-by-one error in loop iterations
• Confusing popped value with pushed values

4. Consider the following buggy code for finding the k-th smallest sum of pairs from two sorted arrays. Which line contains the subtle bug that can cause incorrect results or runtime errors?

def countPairs(nums1, nums2, mid):
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low < high:
        mid = (low + high) // 2
        if countPairs(nums1, nums2, mid) <= k:  # Bug here
            low = mid + 1
        else:
            high = mid
    return low

medium

A. Line with 'j = len(nums2) - 1' initialization

B. Line with 'count += (j + 1)' inside countPairs

C. Line with 'while j >= 0 and nums1[i] + nums2[j] > mid:' condition

D. Line with 'if countPairs(nums1, nums2, mid) <= k:' in kthSmallestSum

Solution

1. Step 1: Understand binary search condition

   Correct condition is countPairs(...) < k to move low up; using ≤ k skips valid sums.

2. Step 2: Effect of bug

   Using ≤ k causes binary search to overshoot and miss the exact k-th sum, returning incorrect result.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing ≤ to < fixes correctness [OK]

Hint: Binary search must use strict less-than for correct convergence [OK]

Common Mistakes:

• Using ≤ instead of < in binary search condition
• Off-by-one errors in countPairs

5. The following code attempts to sort a k-sorted array using a min-heap. Identify the bug that causes incorrect or incomplete output.

medium

A. Line initializing the heap with arr[:k+1] is incorrect; should be arr[:k].

B. The for-loop range should be from 0 to len(arr), not k+1 to len(arr).

C. Using heapq.heappush instead of heappop in the loop causes wrong heap operations.

D. The code does not extract remaining elements from the heap after the for-loop.

Solution

1. Step 1: Analyze heap initialization and loop

   Heap is correctly initialized with first k+1 elements; loop pushes and pops correctly.

2. Step 2: Check for extraction after loop

   After the loop, remaining elements in heap are not popped and placed back into arr, causing incomplete output.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing final extraction leads to missing sorted elements [OK]

Hint: Always pop remaining heap elements after main loop [OK]

Common Mistakes:

• Forgetting to pop leftover heap elements
• Incorrect heap size initialization
• Misusing heap push/pop functions