Merge two sorted arrays

Problem statement

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.

Constraints

• 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>

Examples

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]

Sudo Code

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

Dry Run

Solution

 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 Analysis

• Time Complexity: O(m + n)

• Space Complexity: O(1)

Topics Covered

Two Pointers

Companies

Amazon, Goldman Sachs, Linkedin, Microsoft, Visa