Coding Interview PatternsMerge Sorted Array
EasyK-way Merge

Merge Sorted Array

Explanation & Solution

Practice Problem

Description

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and 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. nums1 has a length of m + n, where the last n elements are set to 0 and should be ignored.

Input:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
0
1
1
2
2
3
3
0
4
0
5
0
0
2
1
5
2
6
Output:[1,2,2,3,5,6]
0
1
1
2
2
2
3
3
4
5
5
6

Explanation: The arrays are merged into [1,2,2,3,5,6].

Constraints

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • -10^9 <= nums1[i], nums2[j] <= 10^9

Approach

K-way Merge pattern

1. Use Three Pointers From the End

  • p1 starts at the last valid element of nums1 (index m - 1)
  • p2 starts at the last element of nums2 (index n - 1)
  • p is the write pointer starting at the last position of nums1 (index m + n - 1)
  • Writing from the back avoids overwriting elements we still need

2. Fill From Largest to Smallest

  • While p2 >= 0, compare nums1[p1] and nums2[p2]
  • Place the larger value at nums1[p] and move both the chosen source pointer and p backward
  • If nums1 is exhausted (p1 < 0), keep copying from nums2

3. Remaining Elements

  • If p1 still has elements when p2 is exhausted, they are already in place — no work needed
  • If p2 still has elements, the else branch copies them

Key Insight

  • The key insight is to iterate backwards so we use the spare space without clobbering unprocessed elements
Time
O(m + n)each element is written exactly once
Space
O(1)no extra array; we write into the trailing zeros of `nums1`

Visualization

Input:
[1, 2, 3, 0, 0, 0], m = 3
102132030405
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Merge Two Sorted Lists
Next
Merge K Sorted Lists