DEV Community 👩‍💻👨‍💻

sachin26
sachin26

Posted on

Striver's SDE Sheet Journey - #9 Merge two sorted Arrays

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.

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]
Enter fullscreen mode Exit fullscreen mode

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

Solution 1

sort the num1 array by swapping num2 array elements, while swapping keep sorting num2, then add all num2 elements to num1 array.

lets understand this approach step by step.

step-1 Initialise two varible pointer1 = 0 & pointer2 = 0.

step-2 if n == 0 , then return.

step-3 run a loop from i=1 to m,then

if num1[pointer1] > num2[pointer2],then

1. swap(num1[pointer1],num2[pointer2]).
2. sort the num2 array.
3. increment pointer1++

else increment pointer1++

step-4 again run a loop from i=1 to n,then

1. num1[pointer1] = num2[pointer2]
2. increment the pointer2++.

step-5 end.

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pointer1=0, pointer2=0;

        if(n==0) return;

        for(int i=0; i<m;i++){
            if(nums1[pointer1] > nums2[pointer2]){
                int temp = nums1[pointer1];
                nums1[pointer1] = nums2[pointer2];
                nums2[pointer2] = temp;
                Arrays.sort(nums2);
                pointer1++;
            }else
            pointer1++;

        }


            for(int i=1;i<=n;i++){
                nums1[pointer1] = nums2[pointer2];
                pointer1++;
                pointer2++;
            }

    }
}
Enter fullscreen mode Exit fullscreen mode

Solution 2

by reverse sorting, this problem can be solved in linear time complexity.

step-1 initialise variables i=m-1, j=n-1, arr1Len=nums1.length-1.

step-2 run a loop if i>=0 and j>=0, then

if nums1[i] > nums2[j], then
update the value from the last index.
nums1[arr1Len] = nums[i];
i--
arr1Len--
else
nums1[arr1Len] = nums[j]
j--
arr1Len--

srep-3 run a loop if j >=0, then

nums1[arr1Len] = nums[j]
arr1Len--
j--

step-4 end.

Java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
      int i=m-1,j=n-1,arr1Len=nums1.length-1;

        while(i>=0 && j>=0){
            if(nums1[i] > nums2[j]){
                nums1[arr1Len] = nums1[i];
                i--;
                arr1Len--;
            }else{
                nums1[arr1Len] = nums2[j];
                j--;
                arr1Len--;
            }
        }

        while(j>=0){
            nums1[arr1Len] = nums2[j];
            j--;
            arr1Len--;
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity : O(m+n)

Space Complexity : O(1)

Thank you for reading this article. if you find something wrong, let me know in the comment section.

Top comments (1)

DEV

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.