88 Merge Sorted Array
Last updated
Last updated
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
.
For the whole problem statement, please .
Use three pointers to compare the elements from the end of both arrays and place the larget element at the end of nums1
.
Since nums1
has enough space to accomodate all elements from both arrays, we can start merging from the end of nums1
to avoid overwriting elements that have not been processed yet.
After one of the arrays is fully processed, copy any remaining elements from the other array into nums1
.
Initialization
We initialize the three pointers p1
for the last valid elements in nums1
, p2
for the last elements in nums2
, and p
for the last position in the merged array nums1
.
Merging from the End
We use while
loop to compare the elements from the end of the both arrays (nums1
and nums2
). The loop continues as long as there are elements left in both arrays (p1 >= 0
and p2 >= 0
).
Inside the loop, we compare the elements at nums1[p1]
and nums2[p2]
. The larger element is placed at the nums1[p]
, and the corresponding pointer (p1
or p2
) is decremented.
Handling the Remaining Elements
After the main loop, if there are any remaining elements in nums2
(i.e., p2 >= 0
), we copy them to the beginning of nums1
. This is because all the elements is nums1
have already been processed and moved to their correct positions.
We use another while
loop to copy the remainng elements from nums2
to nums1
. The loop continues as long as there are elements left in nums2
(p2 >= 0
).