0088 - Merge Sorted Array (Easy)

Problem Link

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

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.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Approach 1: Brute Force

Since, this problem is under easy category, we know $nums1$ has length $m + n$ so we add the elements of $nums2$ in the empty spaces of $nums1$. Finally, we sort the $nums1$ with any standard sorting algorithm. This solution gives $O(N log N)$ time complexity and $O(1)$ space complexity.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // adding elements of nums2 at empty places of nums1
        // starting at index m
        for(int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        // sorting nums1 in an ascending order
        Arrays.sort(nums1);
    }
}

Approach 2: Two Pointers

A better way to do it is using one-pass two pointer approach. We make a copy of $nums1$ into $temp$, then iterate through both arrays $nums2$ and $temp$ comparing their elements in ascending fashion with the help of two pointers $i$ and $j$,simultaneouslty adding the smaller elements into $nums1$. Finally, the bigger elements out of either $nums2$ or $temp$ are going to be added by seperately iterating over them if $i$ or $j$ satisfies the conditions. This solution gives $O(m + n)$ or $O(n)$ time complexity and $O(m)$ or $O(n)$ space complexity.

class Solution {
    public void merge(int[] nums1 , int m , int[] nums2 , int n) {
        int i = 0, j = 0, k = 0;
        // making a temp copy of nums1, for easier swapping of elements
        int[] temp = Arrays.copyOfRange(nums1 , 0 , m);
        // loop till anyone array elements exhausts
        while (i < m && j < n) {
            // adding the elements into nums1 in ascending order
            if (temp[i] < nums2[j]) {
                nums1[k] = temp[i];
                i++;
            } else {
                nums1[k] = nums2[j];
                j++;
            }
            k++;
        }
        // now adding the left out elements either of temp or nums2
        // Either one of the loops will execute because every time one array's length
        // would come out to be shorter than the other one
        while (i < m) {
            nums1[k] = temp[i];
            k++;
            i++;
        }
        while (j < n) {
            nums1[k] = nums2[j];
            k++;
            j++;
        }
    }
}

Approach 3: Two Pointers In-place (Optimal)

As we know, $nums1$ can hold size of $m + n$ array, which can have empty slots at the end to move $nums2$ array.

Since the array is already sorted, we can place the elements from highest to lowest in $nums1$ by moving from last slot to first.

Time Complexity: $O(m + n)$, where, $m$ - length of nums1, $n$ - length of nums2

Space complexity: $O(1)$

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // index position for array placements
        int idx = nums1.length - 1; m -= 1; n -= 1;
        while (n >= 0) {
            // Place elements from right direction to left.
            if (m >= 0 && nums1[m] > nums2[n]) {
                nums1[idx] = nums1[m--];
            } else {
                nums1[idx] = nums2[n--];
            }
            idx--;
        }
    }
}

Approach 4: Shell sort

1. Calculate the gap value for merging the two arrays. The gap is determined as $\lceil \frac{{\text{size of arr1} + \text{size of arr2}}}{{2}} \rceil$.

2. Initialize two pointers: the left pointer at index $0$ and the right pointer at index (left + gap).

3. Perform the following steps for each gap until the gap becomes $0$:

   • Inside a loop that continues until the right pointer reaches the end (i.e., index $n + m$), handle three different cases:
     • If the left pointer is inside $\text{arr1}$ and the right pointer is in $\text{arr2}$, compare $\text{arr1}[{\text{left}}]$ and $\text{arr2}[{\text{right}} - n]$. If $\text{arr1}[{\text{left}}] > \text{arr2}[{\text{right}} - n]$, swap them.
     • If both pointers are in $\text{arr2}$, compare $\text{arr1}[{\text{left}} - n]$ and $\text{arr2}[{\text{right}} - n]$. If $\text{arr1}[{\text{left}} - n] > \text{arr2}[{\text{right}} - n]$, swap them.
     • If both pointers are in $\text{arr1}$, compare $\text{arr1}[{\text{left}}]$ and $\text{arr2}[{\text{right}}]$. If $\text{arr1}[{\text{left}}] > \text{arr2}[{\text{right}}]$, swap them.

4. After the right pointer reaches the end, decrease the value of the gap by setting it to $\lceil \frac{{\text{current gap}}}{{2}} \rceil$.

5. Repeat the loop until the gap becomes $0$.

6. Finally, after performing all the operations, you will have the merged sorted array.

class Solution {
 public:
  void swapIfGreater(vector<int>& arr1, vector<int>& arr2, int ind1, int ind2) {
    if (arr1[ind1] > arr2[ind2]) {
      swap(arr1[ind1], arr2[ind2]);
    }
  }
  void merge(vector<int>& arr1, int n, vector<int>& arr2, int m) {
    int len = n + m;
    // initial gap:
    int gap = (len / 2) + (len % 2);
    while (gap > 0) {
      // place 2 pointers:
      int left = 0, right = left + gap;
      while (right < len) {
        // case 1: left in arr1 and right in arr2:
        if (left < n && right >= n) swapIfGreater(arr1, arr2, left, right - n);
        // case 2: both pointers in arr2:
        else if (left >= n) swapIfGreater(arr2, arr2, left - n, right - n);
        // case 3: both pointers in arr1:
        else swapIfGreater(arr1, arr1, left, right);
        left++, right++;
      }
      // break if iteration gap=1 is completed:
      if (gap == 1) break;
      // otherwise, calculate new gap:
      gap = (gap / 2) + (gap % 2);
    }
    int j = 0;
    for (int i = n; i < n + m; i++) {
      arr1[i] = arr2[j];
      j++;
    }
  }
};