Merge two sorted arrays into nums1 in-place without using extra space.

Problem Statement

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. The array `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. Return the merged `nums1`.

Examples

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

Output: [1, 2, 2, 3, 5, 6]

Explanation: Combining the input according to Merge two sorted arrays without extra space logic yields [1, 2, 2, 3, 5, 6].

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

Output: [1]

Explanation: Combining the input according to Merge two sorted arrays without extra space logic yields [1].

Complexity

Time Complexity: O(M + N)

Space Complexity: O(1)

Hints

💡 Hint 1: nums1 has total length m + n, with the last n slots empty (zeroes). 💡 Hint 2: Fill nums1 from the back (index m + n - 1) towards the front to avoid overwriting elements. 💡 Hint 3: Compare nums1[p1] and nums2[p2], placing the larger value at nums1[p] and decrementing pointers.

Editorial & Approach

Problem Overview & Intuition

Merging from the beginning would overwrite unprocessed elements in nums1. By merging from the back (index m + n - 1), we write to currently empty space, achieving O(M + N) time with O(1) extra space.

Step-by-Step Approach

Set p1 = m - 1, p2 = n - 1, and write pointer p = m + n - 1.
While p1 >= 0 && p2 >= 0, place the larger of nums1[p1] and nums2[p2] into nums1[p] and decrement.
Drain remaining elements of nums2 into nums1.
Return nums1.

Optimal Implementation (JavaScript)

function mergeSortedArrays(nums1, m, nums2, n) {
  let p1 = m - 1, p2 = n - 1, p = m + n - 1;
  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1--];
    } else {
      nums1[p] = nums2[p2--];
    }
    p--;
  }
  while (p2 >= 0) nums1[p--] = nums2[p2--];
  return nums1;
}

Complexity Analysis

Time Complexity O(M + N) — each element moved once.

Space Complexity O(1) — in-place modification of nums1.

Edge Cases & Corner Traps Handled

m = 0: nums1 filled entirely from nums2.
n = 0: nums1 remains unchanged.

Merge two sorted arrays without extra space

Hard

Example Scenarios

1Example 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:

Combining the input according to Merge two sorted arrays without extra space logic yields [1, 2, 2, 3, 5, 6].

2Example 2

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

Output: [1]

Explanation:

Combining the input according to Merge two sorted arrays without extra space logic yields [1].

Editor

Loading Editor...

nums1 =

[1, 2, 3, 0, 0, 0]

m =

nums2 =

[2, 5, 6]

n =

Output:Click "Run" above to execute and verify your code here.

[1,2,2,3,5,6]