Merge K Sorted Arrays

▶

Steps

setup

Initialize arrays for merging

Start with the input arrays: [1,4,5], [1,3,4], and [2,6]. These are the arrays to be merged.

💡 Initialization sets the stage for merging by identifying the arrays to process.

Line:

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

💡 We begin with three sorted arrays that will be merged pairwise.

merge

Merge first pair of arrays: [1,4,5] and [1,3,4]

Begin merging the first two arrays by comparing their first elements: 1 and 1.

💡 Comparing first elements determines which to add first to the merged array.

Line:

if arr1[i] < arr2[j]:

💡 When elements are equal, either can be chosen; here arr2's element is chosen first.

merge

Add 1 from second array to merged array

Add the 1 from the second array to the merged array and advance its pointer.

💡 Adding the smaller or equal element to merged array builds the sorted result.

Line:

merged.append(arr2[j])
j += 1

💡 Advancing pointer in second array after adding its element.

compare

Compare next elements: 1 (first array) and 3 (second array)

Compare current elements 1 from first array and 3 from second array to decide next element to add.

💡 Comparisons decide the order of elements in the merged array.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from first array is chosen next.

merge

Add 1 from first array to merged array

Add 1 from first array to merged array and advance its pointer.

💡 Adding the smaller element maintains sorted order.

Line:

merged.append(arr1[i])
i += 1

💡 Pointer in first array moves forward after adding element.

compare

Compare next elements: 4 (first array) and 3 (second array)

Compare 4 from first array and 3 from second array to decide next element.

💡 Comparison guides which element to add next.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from second array is chosen.

merge

Add 3 from second array to merged array

Add 3 from second array and advance its pointer.

💡 Adding next smallest element continues building merged array.

Line:

merged.append(arr2[j])
j += 1

💡 Pointer in second array moves forward.

compare

Compare next elements: 4 (first array) and 4 (second array)

Compare 4 from both arrays; equal values mean either can be chosen.

💡 Handling equal elements maintains stable order.

Line:

if arr1[i] < arr2[j]:

💡 Stable merge picks from first array when equal.

merge

Add 4 from first array to merged array

Add 4 from first array and advance its pointer.

💡 Adding equal element from first array preserves order.

Line:

merged.append(arr1[i])
i += 1

💡 Pointer in first array moves forward.

compare

Compare next elements: 5 (first array) and 4 (second array)

Compare 5 from first array and 4 from second array to decide next element.

💡 Smaller element is chosen to maintain sorted order.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from second array is chosen.

merge

Add 4 from second array to merged array

Add 4 from second array and advance its pointer.

💡 Adding next smallest element continues the merge.

Line:

merged.append(arr2[j])
j += 1

💡 Pointer in second array moves forward.

merge

Add remaining elements from first array: 5

First array has 5 remaining; add it to merged array.

💡 When one array is exhausted, append remaining elements of the other.

Line:

merged.extend(arr1[i:])

💡 Remaining elements are appended to maintain sorted order.

merge

First pair merged into [1,1,3,4,4,5]

The first two arrays are merged into one sorted array.

💡 Merging pairs reduces the number of arrays to merge next.

Line:

merged_arrays.append(merge_two_arrays(arr1, arr2))

💡 We now have two arrays: the merged one and the third original array.

merge

Merge the two remaining arrays: [1,1,3,4,4,5] and [2,6]

Start merging the merged array with the last array by comparing first elements: 1 and 2.

💡 Final merge combines all arrays into one sorted array.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from merged array chosen first.

merge

Add 1 from merged array to final merged array

Add 1 from merged array and advance its pointer.

💡 Adding smallest element builds final sorted array.

Line:

merged.append(arr1[i])
i += 1

💡 Pointer in merged array moves forward.

compare

Compare next elements: 1 (merged array) and 2 (last array)

Compare 1 from merged array and 2 from last array.

💡 Comparison guides next element to add.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from merged array chosen.

merge

Add 1 from merged array to final merged array

Add 1 from merged array and advance pointer.

💡 Adding next smallest element.

Line:

merged.append(arr1[i])
i += 1

💡 Pointer moves forward in merged array.

compare

Compare next elements: 3 (merged array) and 2 (last array)

Compare 3 from merged array and 2 from last array.

💡 Comparison decides next element.

Line:

if arr1[i] < arr2[j]:

💡 Smaller element from last array chosen.

merge

Add 2 from last array to final merged array

Add 2 from last array and advance pointer.

💡 Adding next smallest element.

Line:

merged.append(arr2[j])
j += 1

💡 Pointer moves forward in last array.

merge

Add remaining elements to final merged array

Append remaining elements [3,4,4,5] from merged array and [6] from last array.

💡 Appending leftovers completes the merge.

Line:

merged.extend(arr1[i:])
merged.extend(arr2[j:])

💡 Final merged array is complete and sorted.

def merge_two_arrays(arr1, arr2):
    i, j = 0, 0  # STEP 2 initialize pointers
    merged = []  # STEP 1 initialize merged array
    while i < len(arr1) and j < len(arr2):  # STEP 3 loop while both arrays have elements
        if arr1[i] < arr2[j]:  # STEP 4 compare elements
            merged.append(arr1[i])  # STEP 5 add from arr1
            i += 1  # STEP 5 advance pointer
        else:
            merged.append(arr2[j])  # STEP 3 add from arr2
            j += 1  # STEP 3 advance pointer
    merged.extend(arr1[i:])  # STEP 12 add leftovers from arr1
    merged.extend(arr2[j:])  # STEP 12 add leftovers from arr2
    return merged  # STEP 13 return merged array

def merge_k_sorted_arrays(arrays):
    if not arrays:
        return []  # STEP 1 handle empty input
    while len(arrays) > 1:  # STEP 2 repeat until one array remains
        merged_arrays = []  # STEP 2 initialize merged arrays list
        for i in range(0, len(arrays), 2):  # STEP 2 pair arrays
            arr1 = arrays[i]  # STEP 2 select first array
            arr2 = arrays[i+1] if i+1 < len(arrays) else []  # STEP 2 select second array or empty
            merged_arrays.append(merge_two_arrays(arr1, arr2))  # STEP 2 merge pair
        arrays = merged_arrays  # STEP 2 update arrays
    return arrays[0]  # STEP 7 return final merged array

if __name__ == '__main__':
    arrays = [[1,4,5],[1,3,4],[2,6]]  # STEP 1 input
    print(merge_k_sorted_arrays(arrays))  # STEP 7 output

📊

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

Watching the step-by-step merging process reveals how divide-and-conquer reduces complexity and how intermediate merges build towards the final sorted array.

insertmin-heap

[1,4,5]

0

[1,3,4]

1

[2,6]

2

peekmin-heap

1

0

1

1

4

2

5

3

3

4

4

5

insertmin-heap

1

0

Added: 1

peekmin-heap

1

0

1

1

3

2

4

3

5

4

4

5

insertmin-heap

1

0

1

1

Added: 1

peekmin-heap

1

0

1

1

3

2

4

3

5

4

4

5

insertmin-heap

1

0

1

1

3

2

Added: 3

peekmin-heap

1

0

1

1

3

2

4

3

5

4

4

5

insertmin-heap

1

0

1

1

3

2

4

3

Added: 4

peekmin-heap

1

0

1

1

3

2

4

3

5

4

4

5

insertmin-heap

1

0

1

1

3

2

4

3

4

4

Added: 4

insertmin-heap

1

0

1

1

3

2

4

3

4

4

5

5

Added: 5

insertmin-heap

[1,1,3,4,4,5]

0

[2,6]

1

peekmin-heap

1

0

2

1

6

2

1

3

3

4

4

5

4

6

5

7

insertmin-heap

1

0

Added: 1

peekmin-heap

1

0

2

1

6

2

3

3

4

4

4

5

5

6

insertmin-heap

1

0

1

1

Added: 1

peekmin-heap

1

0

1

1

2

2

6

3

3

4

4

5

4

6

5

7

insertmin-heap

1

0

1

1

2

2

Added: 2

extract_minmin-heap

1

0

1

1

2

2

3

3

4

4

4

5

5

6

6

7

Key Takeaways

✓ Merging pairs of arrays repeatedly reduces the problem size efficiently.

This divide-and-conquer approach is clearer when visualized step-by-step than just reading code.

✓ Comparing elements one-by-one and advancing pointers is the core of merging sorted arrays.

Seeing pointer movements and comparisons visually helps understand how sorted order is maintained.

✓ Handling leftover elements after one array is exhausted ensures all elements are included.

This step is easy to miss in code but critical for correctness; visualization highlights it.

Practice

1. You are given k sorted linked lists and need to merge them into one sorted list efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Concatenate all lists into one and then sort the combined list using a comparison-based sort.

B. Use a greedy approach by repeatedly picking the smallest head node among all lists without any auxiliary data structure.

C. Apply a divide and conquer strategy by recursively merging pairs of lists until one remains.

D. Use dynamic programming to store intermediate merged results and build the final list.

Solution

1. Step 1: Understand the problem constraints

   We have k sorted lists and want to merge them efficiently.

2. Step 2: Analyze each approach's time complexity

   Greedy without auxiliary structures leads to O(kN) per extraction, concatenation then sorting is O(N log N), dynamic programming is not applicable here. Divide and conquer merges pairs in O(N log k) time, which is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer merges pairs efficiently [OK]

Hint: Divide and conquer merges pairs in O(N log k) time [OK]

Common Mistakes:

• Assuming greedy without heap is efficient
• Thinking sorting concatenated list is optimal
• Confusing DP applicability here

2. What is the time complexity of the optimal approach that assigns n jobs to K machines using event sorting and a single min-heap to track running jobs?

medium

A. O(n * K) because each job may check all machines for availability.

B. O(n log n) because sorting jobs dominates and heap operations are constant time.

C. O(n log K) because jobs are sorted and each heap operation on K machines costs log K.

D. O(n + K) because heap operations are amortized to constant time.

Solution

1. Step 1: Analyze sorting step

   Sorting jobs by start time takes O(n log n).

2. Step 2: Analyze heap operations

   Each job causes at most one pop and one push on the min-heap of size at most K, costing O(log K) per job.

3. Step 3: Combine complexities

   Since K ≤ n generally, O(n log n) sorting and O(n log K) heap operations combine to O(n log n). But since K ≤ n, and the problem emphasizes K machines, the heap operations dominate as O(n log K).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Heap operations scale with log K, sorting with log n; overall O(n log K) [OK]

Hint: Heap operations cost log K, not linear K [OK]

Common Mistakes:

• Confusing heap size as n instead of K
• Ignoring sorting cost or assuming heap ops are constant time
• Assuming linear scan per job leads to O(nK)

3. What is the time complexity of the optimal min-heap based algorithm to find the nth super ugly number given k primes?

medium

A. O(n log k) -- because each of the n iterations involves a heap operation on size k

B. O(nk) -- because each of the n ugly numbers is generated by multiplying with k primes

C. O(n log n) -- because the heap size grows with n as new numbers are pushed

D. O(k log n) -- because k primes are processed with log n complexity each

Solution

1. Step 1: Identify heap size and operations per iteration

   The heap size is fixed at k, as each prime contributes one element at a time.

2. Step 2: Calculate total complexity

   For n ugly numbers, each iteration pops and pushes one element, each heap operation O(log k), total O(n log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size does not grow with n, so complexity depends on k, not n [OK]

Hint: Heap size fixed at k -> O(n log k) time [OK]

Common Mistakes:

• Assuming heap grows with n, leading to O(n log n)
• Confusing k and n in complexity
• Ignoring heap operation cost

4. Suppose the problem changes so that elements from the arrays can be reused multiple times to form sums (i.e., pairs can include the same element multiple times). Which modification to the binary search approach is necessary to correctly find the k-th smallest sum?

hard

A. No modification needed; reuse does not affect counting pairs.

B. Use a min-heap approach with a visited set to handle duplicates and reuse correctly.

C. Modify countPairs to count pairs with replacement by resetting pointer j for each i.

D. Use binary search but countPairs must be replaced with a formula counting sums with repetition.

Solution

1. Step 1: Understand reuse effect on counting

   With reuse allowed, pairs are not limited to unique indices; counting must consider all j for each i.

2. Step 2: Modify countPairs

   Resetting j for each i allows counting all pairs with sums ≤ mid including repeated elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting j ensures correct counting with reuse [OK]

Hint: Reusing elements breaks monotonic pointer j; must reset per i [OK]

Common Mistakes:

• Assuming original countPairs works with reuse
• Using heap without visited set causes duplicates

5. Suppose the problem is modified so that elements in the lists can be reused multiple times (i.e., you can pick the same element multiple times from the same list). Which modification to the optimal min-heap approach correctly handles this variant?

hard

A. Continue using the min-heap approach but do not advance the index in the list after pushing the next element, allowing reuse of the same element.

B. Use a min-heap but track counts of elements used per list and only advance indices when all elements have been used once.

C. Modify the algorithm to allow pushing the same element multiple times without advancing the index, but update current_max accordingly to avoid infinite loops.

D. The min-heap approach cannot be adapted; instead, use a dynamic programming approach to handle reuse.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means the same element can be counted multiple times, so indices alone do not track usage.

2. Step 2: Modify tracking mechanism

   Tracking counts of usage per list and advancing indices only after all elements are used once prevents infinite loops and ensures coverage.

3. Step 3: Why other options fail

   Not advancing indices leads to infinite loops; pushing same element multiple times without control breaks correctness; DP is inefficient here.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking usage counts ensures correct reuse handling [OK]

Hint: Track usage counts per list to handle reuse correctly [OK]

Common Mistakes:

• Not advancing indices causing infinite loops
• Pushing duplicates without control
• Switching to DP unnecessarily