Explorer
JavaScript

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

  1. Set p1 = m - 1, p2 = n - 1, and write pointer p = m + n - 1.
  2. While p1 >= 0 && p2 >= 0, place the larger of nums1[p1] and nums2[p2] into nums1[p] and decrement.
  3. Drain remaining elements of nums2 into nums1.
  4. 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
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`.
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 =
3
nums2 =
[2, 5, 6]
n =
3
Output:Click "Run" above to execute and verify your code here.
[1,2,2,3,5,6]