Merge two sorted arrays in-place
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
You are given two sorted integer arrays `nums1` and `nums2`, both sorted in non-decreasing order.
- `nums1` has length `m + n`. The first `m` elements hold the sorted data; the last `n` elements are placeholders (for example, zeros) and should be ignored.
- `nums2` has length `n` and holds `n` sorted elements.
Merge `nums2` into `nums1` so that `nums1` becomes a single array of length `m + n` sorted in non-decreasing order.
The interviewer probes the following:
1. **Core merge.** Perform the merge **in-place** inside `nums1`, using only **O(1)** additional space (you may not allocate a new array proportional to the input) and **O(m + n)** time.
2. **Algorithm and direction.** Describe your approach in detail and explain why merging from the *end* (filling the largest elements into the back of `nums1` first) lets you avoid overwriting unprocessed data. Coding may or may not be required — be ready to walk through the logic verbally either way.
3. **Complexity analysis.** State and justify the time and space complexity of your solution.
4. **Edge cases.** Discuss and test cases such as: `nums2` empty (`n = 0`), `nums1` empty (`m = 0`), all elements equal, and when every element of one array is strictly less than every element of the other (so one array is exhausted before the other).
Quick Answer: Merge two sorted arrays in-place evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order, along with two integers `m` and `n`.
- `nums1` has length `m + n`. The first `m` elements hold the sorted data; the last `n` slots are placeholders (e.g. zeros) and should be ignored.
- `nums2` has length `n` and holds `n` sorted elements.
Merge `nums2` into `nums1` so that `nums1` becomes a single array of length `m + n` sorted in non-decreasing order. Do the merge **in-place** inside `nums1`, using only **O(1)** extra space and **O(m + n)** time. Return the merged `nums1`.
The key insight is to fill `nums1` from the **back**: by writing the largest remaining element into the last open slot and moving inward, you never overwrite an element of `nums1` you have not yet read, so no temporary copy is needed.
**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]
```
**Example 2**
```
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
```
**Example 3**
```
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
```
Constraints
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 400
- -10^9 <= nums1[i], nums2[j] <= 10^9
- The first m elements of nums1 and all of nums2 are sorted non-decreasing
Examples
Input: ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)
Expected Output: [1, 2, 2, 3, 5, 6]
Explanation: Standard interleave: merging [1,2,3] and [2,5,6] yields [1,2,2,3,5,6].
Input: ([1], 1, [], 0)
Expected Output: [1]
Explanation: nums2 is empty (n=0); nums1 is already complete and unchanged.
Hints
- A forward merge into nums1[0] would overwrite elements of nums1 you have not yet compared. Which direction avoids that?
- Use three pointers: i at the last real element of nums1 (index m-1), j at the last element of nums2 (index n-1), and k at the last slot of nums1 (index m+n-1). Write the larger of nums1[i] and nums2[j] into position k.
- Loop only while j >= 0. Once nums2 is exhausted, any remaining nums1 prefix is already in its correct place, so no extra copying is needed. Guard the read with i >= 0 to handle the m = 0 case.