Merge Sorted Array

EASY

Description

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⁹ <= nums1[i], nums2[j] <= 10⁹

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

Approaches

Checkout 3 different approaches to solve Merge Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Merge and Sort

The most straightforward approach is to first merge the two arrays and then sort the resulting array. We can copy the elements of nums2 into the available space at the end of nums1 and then use a standard library sorting function to sort the entire nums1 array.

Algorithm

Copy the n elements from nums2 into nums1 starting from index m.
Use a standard sorting algorithm (like Arrays.sort() in Java) to sort the first m + n elements of nums1.

This method ignores the sorted nature of the input arrays. It first combines the two lists into one and then applies a general-purpose sorting algorithm.

Copy nums2: The n elements of nums2 are copied to the end of nums1, which has n zero-padded slots available from index m to m + n - 1.
Sort nums1: After copying, nums1 contains all the elements from both original arrays, but it is not sorted. A call to a standard sorting function, like java.util.Arrays.sort(), is made to sort the entire nums1 array of length m + n.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Copy elements of nums2 into the end of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        // Sort the entire nums1 array
        java.util.Arrays.sort(nums1);
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Simple to understand and implement.
Leverages highly optimized built-in sorting functions.

Cons:

Inefficient as it doesn't utilize the fact that the input arrays are already sorted.
Time complexity is higher than the optimal solution.

Code Solutions

Checking out 4 solutions in different languages for Merge Sorted Array. Click on different languages to view the code.

class Solution {
public
  void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
      nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }
  }
}

Video Solution

Watch the video walkthrough for Merge Sorted Array

Algorithms:

Sorting

Patterns:

Two Pointers

Data Structures:

Array

Companies:

Accenture |Adobe |Agoda |Amazon |