Merge two sorted arrays

Merge two sorted arrays

Merge two sorted arrays nums1 and nums2 into nums1 of length m + n. The result should be a single sorted array in non-decreasing order. nums1 has m elements at the beginning, followed by n zeros. nums2 has n elements.

  • nums1.length == m + n

  • nums2.length == n

  • 0 <= m, n <= 200

  • 1 <= m + n <= 200

  • -10<sup>9</sup> <= nums1[i], nums2[j] <= 10<sup>9</sup>

nums1 = [1, 3, 5, 7, 9, 0, 0, 0, 0]

nums2 = [2, 4, 6, 8]

Output = [1, 2, 3, 4, 5, 6, 7, 8, 9]

  1. Initialize i, j and k

  2. Comparison between two array elements to fit in correct position

  3. If first array elements is remaining then add it to answer

  4. If second array elements is remaining then add it to answer

 public void merge(int[] nums1, int n, int[] nums2, int m) {

        // Step 1. Initialize i, j and k
        int i = n-1, j = m-1, k = m+n-1;

        // Step 2. Comparison between two array elements to fit in correct positon
        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }

        // Step 3. If first array elements is remaining then add it to ans.
        while(i >= 0){
            nums1[k--] = nums1[i--];
        }

        // Step 4. If second array elements is remaining then add it to ans.
        while(j >= 0){
            nums1[k--] = nums2[j--];
        }
  • Time Complexity: O(m + n)

  • Space Complexity: O(1)

Two Pointers

Amazon, Goldman Sachs, Linkedin, Microsoft, Visa