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]
[code lang="java"]
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    }
}
[code]

Idea – 1

We start with m-1 th and n-1 th elements from nums1 and nums2, whichever is bigger (say nums2) we put that at m+n-1 th place of nums1 and move leftwards in nums2. If we are done processing nums2, we are done. If we are done with nums1 elements, we copy rest of nums2 to the places left in nums1. Time complexity is O(m+n) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1, j = n-1;
        int k = m+n-1;
        
        while(i >= 0 || j >= 0)
        {
            if(j < 0)
            {
                break;
            }
            else if(i < 0 || nums2[j] >= nums1[i])
            {
                nums1[k--] = nums2[j--];
            }
            else
            {
                nums1[k--] = nums1[i--];
            }
        }
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.Memory Usage: 35.5 MB, less than 99.61% of Java online submissions for Merge Sorted Array.

Leave a comment