AlgoViz

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

You have two lists of numbers that are each already sorted from smallest to largest, and you want to combine them into one sorted list without allocating a new array.

The first array, nums1, has room for both lists: its first m slots hold real values and its last n slots are placeholders filled with 0. The second array, nums2, holds n values. Rearrange nums1 in place so that it contains all m + n values in sorted order. Nothing needs to be returned.

Example:

Input: nums1 = [1, 4, 7, 0, 0], m = 3, nums2 = [2, 8], n = 2
Result: nums1 becomes [1, 2, 4, 7, 8]
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 →