Leetcode: 88. Merge Sorted Array

Merge Two Sorted Arrays - An In-Place Solution

Given two sorted arrays nums1 and nums2, you need to merge nums2 into nums1 as one sorted array.

Solution

class Solution {
public:
  void merge(vector& nums1, int m, vector& nums2, int n) {
    vector nums1copy(nums1.begin(), nums1.begin() + m);

    int frontPtr1 = 0, frontPtr2 = 0;
    int totalLength = 0;

    while (frontPtr1 < m && frontPtr2 < n) {
      if (nums1copy[frontPtr1] <= nums2[frontPtr2]) {
        nums1[totalLength] = nums1copy[frontPtr1];
        frontPtr1++;
      } else {
        nums1[totalLength] = nums2[frontPtr2];
        frontPtr2++;
      }
      totalLength++;
    }

    while (frontPtr1 < m) {
      nums1[totalLength] = nums1copy[frontPtr1];
      frontPtr1++;
      totalLength++;
    }

    while (frontPtr2 < n) {
      nums1[totalLength] = nums2[frontPtr2];
      frontPtr2++;
      totalLength++;
    }
  }
};
  

Explanation

The given solution merges two sorted arrays nums1 and nums2 into nums1 as one sorted array. It uses two pointers (frontPtr1 and frontPtr2) to iterate over the elements of nums1copy and nums2 and merges them into nums1.

The solution works as follows:

• Create a copy of the first m elements of nums1 in a new vector nums1copy.
• Initialize two pointers frontPtr1 and frontPtr2 to track the current positions in nums1copy and nums2, respectively.
• Initialize a total length variable to keep track of the merged array length.
• Compare the elements at frontPtr1 in nums1copy and frontPtr2 in nums2. Select the smaller element and place it in the merged array at the corresponding position. Increment the respective pointers and the total length.
• If there are remaining elements in nums1copy or nums2 after merging, add them to the end of the merged array.

Complexity Analysis

The time complexity of the solution is O(m+n), where m and n are the lengths of nums1 and nums2, respectively. The solution traverses both arrays once to merge the elements.

The space complexity is O(m) as we create a copy of nums1 to store the initial elements.