Merge two Sorted Arrays in O(m+n) Time

help
,
1

Problem Link : Merge Two Sorted Arrays - LeetCode

The Code below is giving wrong answers on compilation, but when I try out things on paper, the logic looks fine to me, Can Someone help me to find out the reason why this code is not working as assumed ?

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

in your last else condition you are including the equal values in both array1 and array 2 only once . In the question, I think we have to make nums1 as the sorted array. You can create a new array and store the sorted values in it and then copy it into nums1.

3

Your code will produce wrong answer because of this line :

i++; j++; k++;

If numbers in both vectors (at index i and j) is same, you should update either i or j, not both, because if you do so, one of your element will be lost.
And yes don’t overwrite num1, store in a new vector.

1 Like