1. Problem Statement (Simple Explanation)
You’re given:
nums1: an integer array of length m + n
The first m elements are valid, sorted in non-decreasing order.
The last n elements are placeholders (zeros) to accommodate merging.
nums2: an integer array of length n, sorted in non-decreasing order.
Integers m and n: number of valid elements in nums1 and nums2.
You must:
Merge nums2 into nums1, so that the first m + n elements of nums1 become a sorted array.
Do this in-place (modify nums1, don’t return a new array).
Time complexity O(m + n) is required.
2. Examples
Example 1:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Arrays to merge:
[1,2,3] and [2,5,6]
Result:
[1,2,2,3,5,6]
Output (nums1 after): [1,2,2,3,5,6]
Example 2:
Input:
nums1 = [1], m = 1
nums2 = [], n = 0
Nothing to merge; nums1 remains [1].
Output: [1]
Example 3:
Input:
nums1 = [0], m = 0
nums2 = [1], n = 1
We must place all elements from nums2 into nums1.
Output: [1]
3. Approach – Merge from the End (Two Pointers, O(m + n))
Naively merging from the front would require shifting elements, which is expensive.
Instead, we merge from the end:
Use three indices:
i = m - 1 → last valid element in nums1.
j = n - 1 → last element in nums2.
k = m + n - 1 → last position in nums1.
While i >= 0 and j >= 0:
Compare nums1[i] and nums2[j]:
Place the larger at nums1[k].
Move the corresponding pointer (i or j) and k backward.
After main loop:
If j >= 0 (elements still left in nums2), copy all remaining nums2[0..j] into nums1[0..j].
If i >= 0, we don’t need to do anything; the nums1 prefix is already in place.
Pseudo-code:
No need to copy remaining nums1 elements because they are already in place.
Complexity:
Time: O(m + n) – each element is moved at most once.
Space: O(1) – in-place.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment