LeetCode: 88. Merge Sorted Array

The Problem

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.

Examples

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.
Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Solution

We opted for a simple approach using a while loop

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	int cur = nums1.size();

	while(m > 0 && n>0){
		if (nums1[m - 1] >= nums2[n - 1]) {
			nums1[--cur] = nums1[--m];
		} else {
			nums1[--cur] = nums2[--n];
		}
	}

	while(n > 0) nums1[--cur] = nums2[--n];
}

Here's what each part of the code does:

Function Declaration:

• void merge(vector<int>& nums1, int m, vector<int>& nums2, int n): This function takes two sorted integer arrays nums1 and nums2 with sizes m and n respectively. It merges nums2 into nums1 while maintaining the sorted order.

Initialization:

• int cur = nums1.size();: Initialize the variable cur to the size of nums1. This variable will be used to index the elements being merged into nums1.

Merging Process:

• The loop iterates as long as there are elements remaining in both nums1 and nums2:
• It compares the last elements of nums1 and nums2 (nums1[m - 1] and nums2[n - 1] respectively).
• If the last element of nums1 is greater than or equal to the last element of nums2, it moves the last element of nums1 to the current index in nums1 and decrements m.
• Otherwise, it moves the last element of nums2 to the current index in nums1 and decrements n.
• This process continues until one of the arrays is fully processed.

Remaining Elements:

• After the first loop, if there are remaining elements in nums2, the second loop copies them to nums1.
• This loop decrements n and continues until all elements in nums2 are copied to nums1.