Solution by rohitnandi12


  • 0
    R

    Primary Thougths
    It is a simple question but restriction is it should be in-place. In-place modification is when the value of one of the input argument is modified and that is the result.

    Tip:1 Think beyond status quo.
    You may think of using an auxiliary array and later on copy the array back to input array. It is a Naive approach, it is costly and you may not have so much space in memory, so think like a pro.

    Test Cases

    Try to create your own test cases.

    Test Input 1: T1
    [1,1,2,0,0,0]
    6
    [1,2,3]
    3
    
    Test Input 1: T2
    [1,2,3,0,0,0]
    6
    [4,5,6]
    3
    
    Test Input 1: T2
    [4,5,6,0,0,0]
    6
    [1,2,3]
    3
    

    Approach #1

    Intuition

    Tip:2 Solution not always are at the front.
    If you start iterating from front and put the smaller of the two array at the front of array 1, there is possible loss of data as in Test Case 2.
    If you start iterating from back and put the largest number from both the arrays at the end of array 1, you will not loose any data.

    Java

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

    Complexity Analysis

    • Time complexity : $$O(Max(m,n))$$. and not O(m+n) since you are iterating both same time.

    • Space complexity : $$O(1)$$.

    Thank You. Happy Coding :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.