Merging Two Sorted Arrays (In-Place with Two Pointers)

A simple problem with a slight twist

Merging in-place is misleading and wrong in the literal sense but read the problem statement to find out what I mean.

Here’s the problem statement:

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

There are certainly many more ways to do this however most of the solutions I’ve seen online involved three pointers and if they didn’t use three pointers, were most likely done using extra space.

The intuition behind coming up with this solution is removing the trailing zeros while inserting into the first array from the second.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0;
        int p2 = 0;
        while(p1<m+n && p2<n) {
  // this condition is to check whether the p1 pointer has reached the trailing zeros
  // when that condition is reached the number of elements left to be sorted would
  // be equal to the number of elements left to be inserted from nums2
            if(m+n-p1 == n-p2) {
                nums1[p1] = nums2[p2];
                p1++;
                p2++;
            }
else if(nums1[p1]<nums2[p2]) {
                p1++;
            }
   // to insert from nums2 we first remove trailing zero from back and then insert into nums1
            else {
                nums1.pop_back();
                nums1.insert(nums1.begin()+p1, nums2[p2]);
                p2++;
            }
        }
    }
};

However, you must remember that there will be a point when the first pointer meets the trailing zeros, and when it does, you’ll have to fill in the remaining from the second array. So we have this part of the solution handling that case:

if(m+n-p1 == n-p2) {
                nums1[p1] = nums2[p2];
                p1++;
                p2++;
            }

It’s a fairly easy problem, but just be cautious while figuring out the condition when the first pointer reaches the trailing zeros.