88. Merge Sorted Array LeetCode Solution

In this guide, you will get 88. Merge Sorted Array LeetCode Solution with the best time and space complexity. The solution to Merge Sorted Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Merge Sorted Array solution in C++
Merge Sorted Array solution in Java
Merge Sorted Array solution in Python
Additional Resources

88. Merge Sorted Array LeetCode Solution image

Problem Statement of Merge Sorted Array

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

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

Complexity Analysis

Time Complexity: O(m + n)
Space Complexity: O(1)

88. Merge Sorted Array LeetCode Solution in C++

class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1;      // nums1's index (the actual nums)
    int j = n - 1;      // nums2's index
    int k = m + n - 1;  // nums1's index (the next filled position)

    while (j >= 0)
      if (i >= 0 && nums1[i] > nums2[j])
        nums1[k--] = nums1[i--];
      else
        nums1[k--] = nums2[j--];
  }
};
/* code provided by PROGIEZ */

88. Merge Sorted Array LeetCode Solution in Java

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;     // nums1's index (the actual nums)
    int j = n - 1;     // nums2's index
    int k = m + n - 1; // nums1's index (the next filled position)

    while (j >= 0)
      if (i >= 0 && nums1[i] > nums2[j])
        nums1[k--] = nums1[i--];
      else
        nums1[k--] = nums2[j--];
  }
}
// code provided by PROGIEZ

88. Merge Sorted Array LeetCode Solution in Python

class Solution:
  def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i = m - 1  # nums1's index (the actual nums)
    j = n - 1  # nums2's index
    k = m + n - 1  # nums1's index (the next filled position)

    while j >= 0:
      if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]
        k -= 1
        i -= 1
      else:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1
 # code by PROGIEZ