Skip to main content

88. Merge Sorted Array

easy

Merge two sorted integer arrays in-place into the first array. Tests two-pointer mechanics and the trick of filling from the back to avoid overwrites.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

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

Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result is merged into nums1 in-place.

Example 2

Input
nums1 = [1], m = 1, nums2 = [], n = 0
Output
[1]

Example 3

Input
nums1 = [0], m = 0, nums2 = [1], n = 1
Output
[1]

Explanation: nums1 contains only the placeholder zero, which gets overwritten.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If you merge from the front, you'll overwrite values in nums1 you haven't compared yet. How can you avoid that?

Hint 2

nums1 has trailing zero slots at the end. What if you fill from the back instead of the front?

Hint 3

Use three pointers: one at index m-1 in nums1, one at n-1 in nums2, and one at m+n-1 for the write position. Compare and write the larger value, decrementing the source pointer.

Solution approach

Reveal approach

Fill nums1 from the back. Maintain three indices: i at m-1 (last real element of nums1), j at n-1 (last element of nums2), and k at m+n-1 (last slot of nums1). At each step compare nums1[i] and nums2[j], write the larger one to nums1[k], and decrement the source pointer plus k. When the loop ends, any leftover elements in nums2 still need to be copied (leftovers in nums1 are already in place). This works because the trailing zero slots are exactly where the largest merged values belong, so we never overwrite a value we still need to read.

Complexity

Time
O(m + n)
Space
O(1)

Related patterns

  • two-pointers
  • in-place

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Meta
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Merge Sorted Array and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →