AlgoViz

Back to All Questions
Merge Sorted Arrays
Meta
Array
Two Pointers
Sorting

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 nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored.

Solution Walkthrough

A common mistake is to start merging from the beginning of nums1. This would require shifting elements and would be inefficient. The optimal approach is to start merging from the end of the arrays.

  1. Initialize three pointers: p1 pointing to the last valid element of nums1 (at index m-1), p2 pointing to the last element of nums2 (at index n-1), and p pointing to the very end of the nums1 array (at index m+n-1).
  2. Use a while loop that continues as long as p2 is non-negative (meaning there are still elements in nums2 to merge).
  3. Inside the loop, compare the elements at nums1[p1] and nums2[p2].
    • If p1 is valid (>= 0) and nums1[p1] is greater than nums2[p2], place nums1[p1] at index p and decrement p1.
    • Otherwise, place nums2[p2] at index p and decrement p2.
  4. Decrement the main pointer p in each iteration.

This approach works because we are filling nums1 from the back, so we never overwrite an element in nums1 that we still need to compare. The time complexity is O(m+n) and the space complexity is O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Related Algorithms
Merge Sort →
Insertion Sort →