Leetcode: Merge Sorted Array

This question is asked at Facebook, Amazon, Microsoft, Apply, LinkedIn, Bloomberg, Shopee, Indeed, among others. It is as follows: 

You are given 2 integer arrays, nums1 and nums2, sorted in non-decreasing order (this means increasing, and 2 integers m and n representing the number or elements in nums1 and nums2 respectively. We want to merge an array in non-decreasing order. Here is how we do it. 

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]

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.

Now let's jump into the code. 

First, let's figure what the pseudocode will look like. 

We can just merge the array and run arrays.sort but it runs in O((n + m) log(n + m)) which isn't going to work in this instance. 

However, this will not work for more complex languages such as C++, so what we do here is keep a 3-pointer approach on how we will solve this problem. The next thing we are going to do is to use 3 pointers. Because each array is sorted we can Achieve time complexity is to initialize make a copy of the nums1 array and then use 2 pointers to write into nums1 array, since that's what we need to do. So we initialize 2 pointers, one for the location of the copy of nums1 and 1 for the location of nums2, both at the beginning of the respective arrays. 

Initialize write pointer at the beginning of nums1. So now we have 2 read pointers and a write pointer. So then after this we compare the pointers of the value and select the least value, then increment the pointers. Remember there are 2 cases if the arrays are filled we have to check first if the pointer is at the end of a particular array before we move on and check the array values to populate.  

 Here is the code in C++:

class Solution {

public:

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

              //assigning everything to the nums1. 

              int nums1Copy[m + 1];

              for(int i = 0; i < m; i++) {

                nums1Copy[i] = nums1[i];

              }

        

              int pointer1 = 0;

              int pointer2 = 0;

             

              for(int p = 0; p < m + n; p++) {  

                  if(pointer2 >= n || (pointer1 < m && nums1Copy[pointer1] < nums2[pointer2])) {

                      nums1[p] = nums1Copy[pointer1]; 

                      pointer1 += 1;

                  } else {

                      nums1[p] = nums2[pointer2];

                      pointer2 += 1;

                  } 

              }

    }

};