Description

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. nums2 has a length of n.

Example 1:

1Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
2Output: [1,2,2,3,5,6]
3Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
4The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

1Input: nums1 = [1], m = 1, nums2 = [], n = 0
2Output: [1]
3Explanation: The arrays we are merging are [1] and [].
4The result of the merge is [1].

Example 3:

1Input: nums1 = [0], m = 0, nums2 = [1], n = 1
2Output: [1]
3Explanation: The arrays we are merging are [] and [1].
4The result of the merge is [1].
5Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

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

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution

In this case, we have to start filling the array from the end. So, we create two pointers p1 and p2 which point to the last element of num1 and num2 respectively. If num2 has no elements, then there is nothing to modify and we break out of the loop. If num1 is not empty and num1 has larger element, then we insert that element at the end of the num1 using index i and reduce the corresponding pointer p1. On the other hand if num2 has element which is larger then we use that element to add at the end and subsequently decrease the pointer p2 to point to next element of num2.

 1class Solution {
 2    public void merge(int[] num1, int m, int[] num2, int n) {
 3        int p1 = m - 1; // pointer for num1
 4        int p2 = n - 1; // pointer for num2
 5        for (int i = m + n - 1; i >= 0; i-- ) {
 6            if (p2 < 0) {
 7                break;
 8            }
 9            if (p1 >= 0 && num1[p1] > num2[p2]) {
10                num1[i] = num1[p1];
11                p1--;
12            } else {
13                num1[i] = num2[p2];
14                p2--;
15            }
16        }
17    }
18}