Problem Description
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.
Key Insights
- The final merged array must maintain sorted order.
- Since nums1 has enough space to accommodate the elements of nums2, we can merge in-place from the end of the arrays.
- Using two pointers starting from the end of the valid elements in nums1 and nums2 allows us to efficiently place the largest elements in the correct position.
Space and Time Complexity
Time Complexity: O(m + n)
Space Complexity: O(1)
Solution
To solve the problem, we will use a two-pointer technique. We will initialize one pointer at the end of the valid elements in nums1 (index m - 1) and another pointer at the end of nums2 (index n - 1). We will also maintain a pointer at the end of nums1 (index m + n - 1) where we will be placing the merged elements. We will compare the elements pointed to by the two pointers, placing the larger one at the end of nums1 and moving the respective pointer backwards. This process will continue until either pointer runs out of elements, at which point we can fill in any remaining elements from nums2.