Merge two sorted arrays in-place
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given two integer arrays sorted in non-decreasing order, and two integers `m` and `n`:
- `nums1` has length `m + n`. The first `m` elements of `nums1` contain valid numbers in sorted order. The last `n` elements of `nums1` are placeholders (you can assume they are set to any values and should be ignored).
- `nums2` has length `n`, and all `n` elements are valid and sorted in non-decreasing order.
Write an algorithm that merges the elements of `nums2` into `nums1` so that `nums1` becomes a single sorted array containing all `m + n` elements, **in-place** (i.e., without using an additional array of size `m + n`).
Return value is not required; modify `nums1` directly.
### Example
Input:
- `nums1 = [1, 3, 5, 0, 0, 0]`, `m = 3`
- `nums2 = [2, 4, 6]`, `n = 3`
After calling your function, `nums1` should become:
- `nums1 = [1, 2, 3, 4, 5, 6]`
### Constraints
- `0 <= m, n <= 10^5`
- `len(nums1) = m + n`
- `len(nums2) = n`
- Arrays are already sorted in non-decreasing order.
Describe the algorithm and then implement it in the language of the interviewer's choice.
Quick Answer: This question evaluates proficiency in array manipulation, in-place merging concepts, and understanding of time and space complexity when combining sorted sequences. Commonly asked in the coding and algorithms domain (arrays/sorting), it tests practical implementation skills and the ability to produce efficient, low-memory solutions while handling ordering constraints and edge cases.
You are given two integer arrays sorted in non-decreasing order, and two integers `m` and `n`:
- `nums1` has length `m + n`. The first `m` elements of `nums1` contain valid numbers in sorted order. The last `n` elements of `nums1` are placeholders and should be ignored.
- `nums2` has length `n`, and all `n` elements are valid and sorted in non-decreasing order.
Merge the elements of `nums2` into `nums1` so that `nums1` becomes a single sorted array containing all `m + n` elements, **in-place** (without allocating a separate array of size `m + n`).
The key insight is to merge from the **back**: compare the largest remaining valid element of `nums1` (index `m-1`) with the largest of `nums2` (index `n-1`) and write the bigger one into the last open slot of `nums1` (index `m+n-1`), walking all three pointers leftward. Filling from the back guarantees you never overwrite a `nums1` element you still need to read.
For verification convenience the function modifies `nums1` and also returns it.
### Example
Input: `nums1 = [1, 3, 5, 0, 0, 0]`, `m = 3`, `nums2 = [2, 4, 6]`, `n = 3`.
After merging, `nums1 = [1, 2, 3, 4, 5, 6]`.
Constraints
- 0 <= m, n <= 10^5
- len(nums1) == m + n
- len(nums2) == n
- Both input arrays are sorted in non-decreasing order
- -10^9 <= nums1[i], nums2[i] <= 10^9 for valid elements
- Merge must be in-place: no auxiliary array of size m + n
Examples
Input: ([1, 3, 5, 0, 0, 0], 3, [2, 4, 6], 3)
Expected Output: [1, 2, 3, 4, 5, 6]
Explanation: Standard interleave: 1<2<3<4<5<6.
Input: ([0], 0, [1], 1)
Expected Output: [1]
Explanation: nums1 has no valid elements (m=0); result is just nums2.
Hints
- If you merge from the front (smallest first), you risk overwriting elements of nums1 you haven't read yet. Try filling positions from the back instead.
- Use three pointers: i at the last valid nums1 element (m-1), j at the last nums2 element (n-1), and k at the very last slot of nums1 (m+n-1).
- At each step write the larger of nums1[i] and nums2[j] into nums1[k], then move that pointer and k left. When nums2 is exhausted (j < 0) you're done — any remaining nums1 elements are already in place.
- Guard against i < 0 (nums1 had no valid elements left) so you fall back to copying the rest of nums2.