C# LeetCode 88: Merge Sorted Array - (Easy)

#tutorial #programming #csharp #leetcode

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.

Constraints:

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

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]

Approach & Initial Thoughts

So we know the two arrays are in non-decreasing order. This means each element is greater than or equal to the previous one. This allows for duplicate values to appear consecutively. For example, the sequence [1, 2, 2, 5, 8] is non-decreasing because 1 < 2 <= 2 < 5 < 8.

Knowing that nums1 already has allocated space for our numbers, we know we'll need to keep track of 3 things.

Last valid element in nums1 (i.e not 0)
Last element in nums2
Index in nums1 where the merged value needs slotting

We merge backwards to avoid overwriting values in nums1.

Compare the elements at nums1[p1] and nums2[p2]
Place the larger one at nums1[pMerge]
Move the corresponding pointer left
Stop once all the nums from nums2 are in place

Code

public void Merge(int[] nums1, int m, int[] nums2, int n)
{
    int p1 = m - 1;
    int p2 = n - 1;
    int pMerge = m + n - 1;

    while (p2 >= 0)
    {
        if (p1 >= 0 && nums1[p1] > nums2[p2])
        {
            nums1[pMerge] = nums1[p1];
            p1--;
        }
        else
        {
            nums1[pMerge] = nums2[p2];
            p2--;
        }

        pMerge--;
    }
}