Merge Sorted Array - LeetCode

The problem is taken from 88. Merge Sorted Array.

Naive approach

In this approach, we use a HashMap(Integer, Integer), where the first place would hold numbers in the array and second place would hold their occurrences.

Code -

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        map<int, int> ump;

        for(int i=0; i<m; i++)
            ump[nums1[i]]++;
        for(int i=0; i<n; i++)
            ump[nums2[i]]++;

        int i = 0;
        for(auto itr=ump.begin(); itr!=ump.end(); itr++) {
            for(int j=0; j<itr->second; j++) {
                nums1[i++] = itr->first;
            }
        }
    }
};

Complexities -

Time complexity - O(n logn). Because sorting happens internally in map, that's why we are able to call a for loop and get the numbers in increasing order.

Space complexity - O(m+n).

Better approach

In this approach the main catch is, we have to start filling the nums1[] array from the back. Hence it will become incredibly easy to solve.

Note - You once try to fill nums1[] array from start and consider different test cases made by yourself. Then you will understand why we are preferring to fill from back.

Code -

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--] = nums2[j--];
            else
                nums1[k--] = nums1[i--];
        }

        while(j>=0)
            nums1[k--] = nums2[j--];
    }
};

Complexities -

Time complexity - O(m+n)

Space complexity - O(1)