Merge Sorted Array

There are countless ways to approach this problem and optimize your solution. In this article, we’ll explore two strategies to tackle this problem. Let’s see the problem statement first.

Problem Statement:

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.

---

Approach 1: Brute Force

The simplest approach is to create a new array, iterate over both input arrays, and insert each element into the new array in sorted order.

1. The function first creates an empty merged array to hold the merged and sorted elements. It then initializes two pointers i and j to point to the first elements of nums1 and nums2, respectively.

2. The function then enters a while loop that compares the elements at nums1[i] and nums2[j] and adds the smaller element to the merged array using the push method. The loop continues until one of the pointers reaches the end of its corresponding array.

3. After the loop, there may be some remaining elements in either nums1 or nums2. The function copies these remaining elements into merged using two additional while loops.

4. Finally, the function copies the sorted elements in merged back into nums1 using a for loop that iterates over the elements in merged and assigns them to the corresponding indices in nums1.

// ES6 Arrow Function
const merge = (nums1, m, nums2, n) => {
    let merged = [];
    let i = 0, j = 0;

    while(i < m && j < n) {
        if(nums1[i] <= nums2[j]) {
            merged.push(nums1[i]);
            i++;
        } else {
            merged.push(nums2[j]);
            j++;
        }
    }

    while(i < m) {
        merged.push(nums1[i]);
        i++;
    }

    while(j < n) {
        merged.push(nums2[j]);
        j++;
    }

    for(let k = 0; k < merged.length; k++) {
        nums1[k] = merged[k];
    }
}

Time Complexity: O((m + n) log(m + n))

Space Complexity: O(m + n)

---

Approach 2: Two-Pointers

1. This is a more optimized approach that involves using two pointers, one for each input array, to merge the arrays in place.

2. Start at the end of both input arrays and work your way backwards, comparing the values at each pointer and inserting the larger value at the end of the first input array.

// ES6 Arrow Function
const merge = (nums1, m, nums2, n) => {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;

    while(i >= 0 && j >= 0) {
        if(nums1[i] >= nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }

        k--;
    }

    while(j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
}

Time Complexity: O(m + n)

Space Complexity: O(1)

---

And there you have it guys! I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 88