# Merge Sorted Array - LeetCode

The problem is taken from  [88. Merge Sorted Array](https://leetcode.com/problems/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)