Merge Sorted Array

▶

Steps

setup

Initialize pointers i, j, and k

Set pointer i to the last valid element index in nums1 (m-1), pointer j to the last element index in nums2 (n-1), and pointer k to the last index of nums1 (m+n-1).

💡 Initializing pointers at the end allows merging from the back, preventing overwriting elements in nums1.

Line:

i = m - 1
j = n - 1
k = m + n - 1

💡 Starting from the end is crucial for in-place merging without extra space.

compare

Compare nums1[i] and nums2[j]

Compare nums1[i] = 3 and nums2[j] = 6 to decide which element to place at nums1[k].

💡 Comparing elements at pointers i and j determines which is larger and should be placed next.

Line:

if nums1[i] > nums2[j]:

💡 The larger element between nums1[i] and nums2[j] goes to nums1[k].

insert

Place nums2[j] at nums1[k]

Since nums2[j] = 6 is larger, place it at nums1[k] (index 5).

💡 Placing the larger element at the end maintains sorted order.

Line:

nums1[k] = nums2[j]
j -= 1

💡 The largest element is placed correctly at the end of nums1.

shrink

Decrement k after placement

Move pointer k one step left to index 4 to prepare for next placement.

💡 Decrementing k moves the merge position backward.

Line:

k -= 1

💡 k always points to the next free position from the end.

compare

Compare nums1[i] and nums2[j] again

Compare nums1[i] = 3 and nums2[j] = 5 to decide next placement.

💡 Each comparison determines which element to place next.

Line:

if nums1[i] > nums2[j]:

💡 The larger element between nums1[i] and nums2[j] is placed next.

insert

Place nums2[j] at nums1[k]

Place nums2[j] = 5 at nums1[k] (index 4).

💡 Placing the larger element maintains sorted order.

Line:

nums1[k] = nums2[j]
j -= 1

💡 The array is gradually filled from the back with the largest remaining elements.

shrink

Decrement k after placement

Move pointer k one step left to index 3 for next placement.

💡 k moves backward after each placement.

Line:

k -= 1

💡 k always points to the next free position.

compare

Compare nums1[i] and nums2[j]

Compare nums1[i] = 3 and nums2[j] = 2 to decide next placement.

💡 Comparisons continue until one array is exhausted.

Line:

if nums1[i] > nums2[j]:

💡 When nums1[i] is larger, place it next.

insert

Place nums1[i] at nums1[k]

Place nums1[i] = 3 at nums1[k] (index 3).

💡 Placing nums1[i] preserves existing elements in place.

Line:

nums1[k] = nums1[i]
i -= 1

💡 Elements from nums1 are shifted right to make room for nums2 elements.

shrink

Decrement k after placement

Move pointer k one step left to index 2 for next placement.

💡 k moves backward after each placement.

Line:

k -= 1

💡 k tracks the next free position from the end.

compare

Compare nums1[i] and nums2[j]

Compare nums1[i] = 2 and nums2[j] = 2 to decide next placement.

💡 Equal elements are handled by placing nums2[j] next.

Line:

if nums1[i] > nums2[j]:

💡 When equal, nums2 element is placed next to maintain stability.

insert

Place nums2[j] at nums1[k]

Place nums2[j] = 2 at nums1[k] (index 2).

💡 Placing nums2 element maintains sorted order and stability.

Line:

nums1[k] = nums2[j]
j -= 1

💡 The merged array is built correctly with duplicates handled.

shrink

Decrement k after placement

Move pointer k one step left to index 1 for next placement.

💡 k moves backward after each placement.

Line:

k -= 1

💡 k tracks the next free position for merging.

prune

Exit main loop since j < 0

Pointer j is -1, meaning nums2 is fully merged. No further copying needed.

💡 When nums2 is exhausted, remaining nums1 elements are already in place.

Line:

while i >= 0 and j >= 0:
    ...
# exit loop
while j >= 0:

💡 No need to copy remaining nums1 elements; they are already sorted and in place.

reconstruct

Final merged array ready

The merged sorted array is now fully formed in nums1: [1, 2, 2, 3, 5, 6].

💡 The algorithm completes with nums1 containing all elements in sorted order.

Line:

print(nums1)

💡 Merging from the end allows in-place merging without extra space.

def merge(nums1, m, nums2, n):
    i = m - 1  # STEP 1
    j = n - 1  # STEP 1
    k = m + n - 1  # STEP 1
    while i >= 0 and j >= 0:  # STEP 2
        if nums1[i] > nums2[j]:  # STEP 8, 11
            nums1[k] = nums1[i]  # STEP 9
            i -= 1  # STEP 9
        else:
            nums1[k] = nums2[j]  # STEP 3, 6, 12
            j -= 1  # STEP 3, 6, 12
        k -= 1  # STEP 4, 7, 10, 13
    while j >= 0:  # STEP 14
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

if __name__ == "__main__":
    nums1 = [1,2,3,0,0,0]
    m = 3
    nums2 = [2,5,6]
    n = 3
    merge(nums1, m, nums2, n)  # STEP 15
    print(nums1)

📊

Merge Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how merging from the end avoids overwriting elements and efficiently merges in-place.

setup

1

0

2

1

j

3

2

0

3

0

4

k

0

5

compare

1

0

2

1

j

3

2

0

3

0

4

k

0

5

insert

1

0

j

2

1

i

3

2

0

3

0

4

k

6

5

move_left

1

0

j

2

1

i

3

2

0

3

k

0

4

6

5

compare

1

0

j

2

1

i

3

2

0

3

k

0

4

6

5

insert

j

1

0

2

1

i

3

2

0

3

k

5

4

6

5

move_left

j

1

0

2

1

i

3

2

k

0

3

5

4

6

5

compare

j

1

0

2

1

i

3

2

k

0

3

5

4

6

5

insert

j

1

0

i

2

1

3

2

k

3

3

5

4

6

5

move_left

j

1

0

i

2

1

k

3

2

3

3

5

4

6

5

compare

j

1

0

i

2

1

k

3

2

3

3

5

4

6

5

insert

1

0

i

2

1

k

2

2

3

3

5

4

6

5

move_left

1

0

k

2

1

2

2

3

3

5

4

6

5

prune

1

0

k

2

1

2

2

3

3

5

4

6

5

reconstruct

1

0

k

2

1

2

2

3

3

5

4

6

5

Result: [1,2,2,3,5,6]

Key Takeaways

✓ Merging from the end avoids overwriting elements in nums1 and allows in-place merging without extra space.

This insight is hard to see from code alone because the pointer directions and array updates are implicit.

✓ The pointers i, j, and k move backward step-by-step, each comparison and placement is crucial to maintain sorted order.

Visualizing each pointer move clarifies the algorithm's flow and why it works.

✓ When elements are equal, the algorithm consistently places nums2's element next, preserving stability.

This subtlety is often missed in code but is clear when watching the step-by-step decisions.

Practice

1. You are given an integer array and a target value. The task is to count the number of triplets in the array such that the sum of the triplet is less than the target. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use three nested loops to check all triplets and count those with sum less than target.

B. Sort the array, then for each element use two pointers to find pairs that form triplets with sum less than target.

C. Use dynamic programming to store counts of sums and build up to triplets.

D. Use a greedy approach by always picking the smallest elements first to form triplets.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting triplets with sum less than a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach that reduces complexity

   Sorting and using two pointers allows scanning pairs efficiently for each fixed element, reducing complexity from O(n^3) to O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two pointers is a classic pattern for 3Sum variants [OK]

Hint: Sorting + two pointers reduces triple loops to quadratic [OK]

Common Mistakes:

• Assuming brute force is optimal
• Thinking DP applies directly here
• Believing greedy always works for sum constraints

2. Consider the following Python function that moves zeroes to the end of the list in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = 0

arr = [0, 2, 0, 1]
moveZeroes(arr)
print(arr)

What is the output after executing this code?

easy

A. [2, 0, 1, 0]

B. [2, 1, 0, 0]

C. [0, 2, 1, 0]

D. [1, 2, 0, 0]

Solution

1. Step 1: Trace first loop with input [0, 2, 0, 1]

   lastNonZeroFoundAt starts at 0. Iteration: num=0 (skip), num=2 (nums[0]=2, lastNonZeroFoundAt=1), num=0 (skip), num=1 (nums[1]=1, lastNonZeroFoundAt=2)

2. Step 2: Fill zeroes from index 2 to end

   nums[2]=0, nums[3]=0. Final array: [2, 1, 0, 0]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Non-zero elements shifted left, zeroes appended [OK]

Hint: Overwrite non-zero elements then fill zeroes after [OK]

Common Mistakes:

• Confusing indices when overwriting
• Forgetting to fill zeroes after lastNonZeroFoundAt

3. What is the time complexity of the optimal two-pointer approach that removes duplicates allowing at most two occurrences in a sorted array of length n?

medium

A. O(n) because each element is processed once with constant time checks

B. O(n²) because of shifting elements when duplicates are removed

C. O(n log n) due to sorting

D. O(1) since it modifies in-place without extra loops

Solution

1. Step 1: Identify the loops and operations

   The algorithm uses a single for loop iterating over n elements once, with constant time operations inside.

2. Step 2: Confirm no nested loops or costly operations

   No nested loops or shifting; elements are overwritten in-place, so no O(n²) behavior.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with constant time per element -> O(n) [OK]

Hint: Single pass with constant checks -> O(n) [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring in-place overwrite cost

4. What is the time complexity of the binary search based solution for Two Sum II -- Input Array Is Sorted, where for each element you perform a binary search for its complement?

medium

A. O(n²)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify outer loop complexity

   Outer loop runs n times, iterating over each element.

2. Step 2: Identify inner binary search complexity

   Binary search runs in O(log n) time for each iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   n iterations x log n binary search -> O(n log n) [OK]

Hint: Outer loop x binary search = n x log n [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming binary search is O(1)
• Ignoring loop inside binary search

5. Suppose the problem is modified so that you can reuse the same line multiple times to form containers (i.e., pairs can include the same index twice). Which of the following statements about adapting the two-pointer approach is correct?

hard

A. The two-pointer approach still works without changes because pointers can point to the same index.

B. The problem reduces to finding the maximum height line squared, so just return height[i] * 0 for some i.

C. A new approach is needed because the two-pointer method relies on distinct indices and cannot handle reuse.

D. You must switch to a brute force approach checking all pairs including identical indices to handle reuse.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means pairs can be (i, i), which the original two-pointer approach does not consider.

2. Step 2: Analyze two-pointer limitations

   The two-pointer method relies on distinct indices moving inward; it cannot handle pairs with the same index, so it must be modified or replaced.

3. Step 3: Evaluate options

   Brute force can handle reuse but is inefficient; simply returning height[i]*0 is incorrect; two-pointer without changes fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two-pointer requires distinct indices -> reuse breaks original approach [OK]

Hint: Two-pointer needs distinct indices; reuse breaks this assumption [OK]

Common Mistakes:

• Assuming two-pointer works unchanged
• Ignoring reuse pairs with same index
• Thinking reuse reduces problem complexity