Merge Sorted Array LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Cisco eBay Facebook Goldman Sachs Google IBM Indeed LinkedIn Microsoft Oracle PayPal Salesforce Uber Visa
Shopee Walmart Global techViews 6060

Problem Statement

Merge Sorted Array LeetCode Solution – 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

Test Case 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.

Approach:

Solution 01

  • We took j=0 to iterate nums2 from the beginning.
  • As we know nums1 has a size of m+n & only the first m elements should be in the final array.
  • So we replace all the elements from the m index with all the elements of nums2.
  • Finally, we’ll sort the array nums1 to get the final sorted array.
  • Time complexity: O(nlogn) //as sorting takes nlogn time.

Solution 02

  • Same logic as Solution 01, But here we used resize().
  • Resize() will simply keep the elements till m index in muns1 array.
  • Then we’ll insert all the elements of the nums2 array by using insert().
  • Lastly, we’ll sort the array nums1 to get the final sorted array.
  • Time complexity: O(nlogn) //as sorting takes nlogn time.

Solution 03

  • As both solutions 01 & 02 take O(nlogn), now we try to solve it with O(n+m).
  • We will use the reverse sorting method.
  • We took 3 variables: i (last valid element of nums1 that will present in the final array), j (last element of nums2) & k ( last index of nums1)
  • First, while loop will compare nums1 & nums2, and the greater element will be in nums1[k].
  • After the loop end if there are still any elements left in an array they will be added by the next 2 while loop.
  • Time complexity: O(m+n).

Merge Sorted Array LeetCode Solution

Code for Merge Sorted Array

Python Program

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, cur = m - 1, n - 1, m + n - 1
        
        while j > -1:
            if i > -1 and nums1[i] >= nums2[j]:
                nums1[cur] = nums1[i]
                i -= 1
            else:
                nums1[cur] = nums2[j]
                j -= 1
            
            cur -= 1

Java Program

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last1 = m-1;
        int last2 = n-1;
        
        int index = nums1.length-1;
        
        while (last1 >=0 && last2>=0) {
            int l = nums1[last1];
            int r = nums2[last2];
            
            if (l < r) {
                nums1[index--] = r;
                last2--;
            } else {
                nums1[index--] = l;
                last1--;
            }
        }
        
        while (last2 >=0) {
            int r = nums2[last2];
            
            nums1[index--] = r;
            last2--;
        }
    }
}

Complexity Analysis for Merge Sorted Array LeetCode Solution

Time Complexity: O(m+n) where m and n are the number of non-zero elements in nums1 and nums2 respectively since we are iterating over both arrays in order to merge them

Space Complexity: O(1) since we are doing the merging in place.

Translate »