Merge Three Sorted Arrays Without Duplicates
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Merge Three Sorted Arrays Without Duplicates
You are given three integer arrays sorted in nondecreasing order. Merge them into one sorted array that contains each distinct value exactly once.
Do not concatenate all three inputs and call a general-purpose sort.
## Function Signature
```python
def merge_three_unique(
first: list[int],
second: list[int],
third: list[int],
) -> list[int]:
...
```
## Constraints
- `0 <= len(first), len(second), len(third) <= 200_000`
- Each input is sorted in nondecreasing order.
- `-1_000_000_000 <= value <= 1_000_000_000` for every array element.
- Inputs may contain duplicates both within and across arrays.
## Examples
```text
Input: first = [1, 2, 2, 7], second = [2, 3, 7], third = [1, 4, 8]
Output: [1, 2, 3, 4, 7, 8]
```
```text
Input: first = [], second = [5, 5], third = []
Output: [5]
```
Quick Answer: Merge three nondecreasing integer arrays into one sorted sequence containing each value exactly once, without falling back to a general-purpose sort. This problem tests linear-time design for large inputs, duplicates within and across arrays, empty cases, boundary exhaustion, and preservation of sorted uniqueness.
You are given three integer arrays `first`, `second`, and `third`, each sorted in nondecreasing order. Merge them into one sorted array that contains each distinct value exactly once, and return it.
The returned array must be in strictly increasing order: every value that appears in at least one input appears exactly once in the output, and no other values appear. If all three inputs are empty, return an empty array.
Do not concatenate all three inputs and call a general-purpose sort. The inputs are already sorted; your merge should exploit that.
**Example 1**
```text
Input: first = [1, 2, 2, 7], second = [2, 3, 7], third = [1, 4, 8]
Output: [1, 2, 3, 4, 7, 8]
```
**Example 2**
```text
Input: first = [], second = [5, 5], third = []
Output: [5]
```
Constraints
- 0 <= len(first), len(second), len(third) <= 200_000
- Each input is sorted in nondecreasing order.
- -1_000_000_000 <= value <= 1_000_000_000 for every array element.
- Inputs may contain duplicates both within and across arrays.
Examples
Input: ([1, 2, 2, 7], [2, 3, 7], [1, 4, 8])
Expected Output: [1, 2, 3, 4, 7, 8]
Explanation: Source example 1: duplicates occur both within one array (2, 2) and across arrays (1, 2, 7).
Input: ([], [5, 5], [])
Expected Output: [5]
Explanation: Source example 2: two arrays are empty and the only populated array holds one duplicated value.
Hints
- The merge step of merge sort combines two sorted arrays in linear time; the same idea extends to three read pointers, one per array.
- At each step, compare the elements the three pointers currently point at and take the smallest one that exists.
- After emitting a value, advance every pointer past all copies of that value so no duplicate can reach the output.