Merge Sorted Array LeetCode Solution

Last updated on January 19th, 2025 at 10:46 pm

Here, we see a Merge Sorted Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Two-Pointers

Companies

Bloomberg, Facebook, Microsoft

Level of Question

Easy

Merge Sorted Array LeetCode Solution

Merge Sorted Array LeetCode Solution

1. 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.

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Two Pointers”. This pattern is commonly used when dealing with sorted arrays or lists, where two pointers are used to traverse the arrays from different directions (e.g., from the end or the beginning) to perform operations like merging, comparing, or finding specific elements.

3. Code Implementation in Different Languages

3.1 Merge Sorted Array C++

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

3.2 Merge Sorted Array Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1 , j = n - 1;
        int 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(i >= 0)
            nums1[k--] = nums1[i--];
        while(j >= 0)
            nums1[k--] = nums2[j--];
        return;        
    }
}

3.3 Merge Sorted Array JavaScript

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m);
    
    var i = 0;
    var j = 0;
    
    while (j < nums2.length) {
        if (nums1[i] === undefined || nums1[i] > nums2[j]) {
            nums1.splice(i, 0, nums2[j]);
            j++;
            i++;
        } else {
            i++;
        }
    } 
};

3.4 Merge Sorted Array Python

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m - 1] > nums2[n - 1]:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1
            else:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
        nums1[:n] = nums2[:n]

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(m + n)O(1)
JavaO(m + n)O(1)
JavaScriptO(m + n)O(n)
PythonO(m + n)O(1)
Scroll to Top