Merge Sorted Array LeetCode Solution: Three-Pointer Walkthrough

Merge Sorted Array (#88) is one of the most frequently asked easy-level interview questions, and it has a beautiful trick hiding inside it. The problem asks you to merge two sorted arrays in place, but the naive left-to-right approach immediately runs into trouble — you overwrite elements you still need.

The insight that unlocks this problem is simple: merge from the END, not the beginning. Since nums1 has empty space at its tail, you can place the largest elements first without ever touching unprocessed data. This reverse-direction merge is the core technique behind the merge sorted array leetcode problem.

This walkthrough covers the three-pointer approach, a visual step-by-step trace, the edge cases interviewers test, and why this "work from the end" idea shows up in many other in-place array problems.

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order. You are also given two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums2 into nums1 as one sorted array, in place.

The key detail: nums1 has a length of m + n. The first m elements are the actual data, and the last n positions are filled with zeroes as placeholders. You must not return a new array — modify nums1 directly so it contains all m + n elements in sorted order.

This constraint is what makes the problem interesting. If you could allocate a new array, you would just do a standard merge. The in-place requirement forces you to think about where to write without destroying data you have not yet read.

The key insight is to reverse your perspective. Instead of merging from left to right (which overwrites unprocessed elements in nums1), merge from right to left. Place the LARGER element at the end of nums1 and work backward.

Set up three pointers: p1 starts at index m - 1 (the last real element in nums1), p2 starts at index n - 1 (the last element in nums2), and a write pointer starts at index m + n - 1 (the very end of nums1). At each step, compare nums1[p1] and nums2[p2], place the larger value at the write position, and decrement the appropriate pointers.

Because you are filling from the end — where the placeholder zeroes live — you never overwrite an element that has not been processed yet. This is the three pointer merge technique, and it runs in O(m + n) time with O(1) extra space.

The implementation is concise once you understand the direction. Initialize p1 = m - 1, p2 = n - 1, and write = m + n - 1. Loop while p2 >= 0 (the critical condition). Inside the loop, if p1 >= 0 and nums1[p1] > nums2[p2], place nums1[p1] at the write position and decrement p1. Otherwise, place nums2[p2] at the write position and decrement p2. Always decrement write.

The loop condition is while p2 >= 0, not while p1 >= 0 AND p2 >= 0. This is intentional. If p2 finishes first, the remaining nums1 elements are already in the correct position — they are sorted and sitting at the front of the array. No further work is needed.

The time complexity is O(m + n) because each element is placed exactly once. The space complexity is O(1) because you only use three pointer variables. This is the optimal leetcode 88 solution.

Let us trace through the classic example: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3. Initialize p1 = 2, p2 = 2, write = 5.

Step 1: Compare nums1[2]=3 vs nums2[2]=6. 6 is larger. Place 6 at index 5. Array: [1, 2, 3, 0, 0, 6]. p2=1, write=4. Step 2: Compare nums1[2]=3 vs nums2[1]=5. 5 is larger. Place 5 at index 4. Array: [1, 2, 3, 0, 5, 6]. p2=0, write=3.

Step 3: Compare nums1[2]=3 vs nums2[0]=2. 3 is larger. Place 3 at index 3. Array: [1, 2, 3, 3, 5, 6]. p1=1, write=2. Step 4: Compare nums1[1]=2 vs nums2[0]=2. Equal, so place nums2[0]=2 at index 2. Array: [1, 2, 2, 3, 5, 6]. p2=-1, write=1.

Now p2 < 0, so the loop ends. The remaining elements [1, 2] in nums1 are already in the correct positions. Final result: [1, 2, 2, 3, 5, 6]. Every element was placed exactly once, and no data was overwritten before being read.

The merge from end approach handles all edge cases gracefully, but interviewers will ask you to walk through them.

nums2 is empty (n = 0): The loop condition p2 >= 0 is immediately false. Nothing happens, and nums1 stays unchanged. This is correct because there is nothing to merge.

nums1 data is empty (m = 0): p1 starts at -1, so the condition p1 >= 0 is always false inside the loop. Every iteration places nums2[p2] at the write position. This effectively copies all of nums2 into nums1, which is exactly what should happen.

All elements of nums2 are smaller than nums1: p1 exhausts before p2. The remaining nums2 elements are placed into the front of nums1. All elements of nums2 are larger: p2 exhausts first, and the original nums1 elements stay in place.

The merge sorted array explained at its core is about reverse-direction thinking. When the obvious left-to-right approach fails because of an in-place constraint, flipping the direction solves the problem elegantly. This same "work from the end" idea appears in many other array problems.

The three pointer merge pattern is a direct descendant of the merge step in merge sort, but adapted for the in-place constraint. If you understand why merging from the end avoids overwriting, you understand a principle that generalizes beyond this single problem.

Practice this technique until the setup — p1 at end of data, p2 at end of second array, write pointer at end of total space — becomes automatic. YeetCode flashcards can help you drill the merge sorted array leetcode pattern so the reverse-merge trick is instant recall in your next interview.