Merge Two Sorted Arrays
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Merge Two Sorted Arrays
Given two integer arrays sorted in nondecreasing order, return a new array containing every value from both inputs in nondecreasing order. Preserve duplicate values.
### Function Signature
```python
def merge_sorted_arrays(a: list[int], b: list[int]) -> list[int]:
```
### Examples
```text
Input: a = [1, 2, 2, 7], b = [2, 3, 8]
Output: [1, 2, 2, 2, 3, 7, 8]
Input: a = [], b = [-2, 0]
Output: [-2, 0]
```
### Constraints
- `0 <= len(a), len(b) <= 200_000`
- Each input is already sorted in nondecreasing order.
- Values fit in signed 64-bit integers.
- Do not mutate either input array.
### Clarifications
- The result length must be `len(a) + len(b)`.
- When equal values are encountered, either input may supply the next copy because only values, not object identity, are observed.
### Hints
- Exploit the ordering instead of sorting the concatenation.
- Target `O(len(a) + len(b))` time and output-sized additional space.
Quick Answer: Merge two nondecreasing integer arrays into a new sorted array while preserving every duplicate. Apply the two-pointer technique for linear time and output-sized space, including empty inputs and equal values, without mutating either source array.
Merge two integer arrays already sorted in nondecreasing order into a new sorted array containing every value and duplicate from both inputs. Do not mutate either input.
Constraints
- Both inputs are sorted in nondecreasing order.
- Either input may be empty.
- Preserve duplicate values.
- The result length is len(a) + len(b).
- Target linear time and output-sized extra space.
Examples
Input: ([], [])
Expected Output: []
Explanation: Two empty arrays merge to empty.
Input: ([], [-2, 0])
Expected Output: [-2, 0]
Explanation: An empty first input contributes no values.
Hints
- Maintain one index into each input.
- Append the smaller current value and advance only its index.
- After one input ends, append the unconsumed suffix of the other.