Challenge Description

https://leetcode.com/problems/merge-sorted-array/

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

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

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

Solution

As usual, merge sorted array is similar with merge sorted link list. But in this challenge, there is a little bit different, we need to finish this with in-place approach, without creating a new array.

If we iterate from left to right, we need to move elements to right(so that we have space for the new inserted element). This will cost too much time.

A excellent idea is loop over from right to left. And don’t forget to handle the remain elements in the longer array.

Time complexity: $O(M+N)$, where M and N are the lengths of two arrays.

class Solution {
public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int last = m + n - 1;
    int i = m-1;
    int j = n-1;
    while(i >= 0 && j >= 0)
      nums1[last--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    while(i >= 0)
      nums1[last--] = nums1[i--];
    while(j >= 0)
      nums1[last--] = nums2[j--];
  }
};

Preparing for an interview? Check out this!