Problem statement
Return the sorted union of two sorted integer arrays. Each value should appear once in the result.
For [1, 1, 3, 5] and [2, 3, 4], return [1, 2, 3, 4, 5].
Constraints & requirements
- INPUT
- Two sorted integer arrays
- RETURN
- A sorted list of distinct values
- TARGET
- One coordinated pass
Examples 3 test cases
Example 1 Overlapping values
- Input
[1, 1, 3, 5] and [2, 3, 4]- Output
[1, 2, 3, 4, 5]
Checks merging and duplicate removal.
Example 2 One empty input
- Input
[] and [2, 2, 4]- Output
[2, 4]
Checks the remaining-elements loop.
Example 3 Same values
- Input
[1, 2] and [1, 2]- Output
[1, 2]
Checks duplicates across both arrays.
Hints Optional
01Compare the smallest remaining values
Because both inputs are sorted, the next result value must be at one of the two pointers.
02Move at least one pointer
Take the smaller current value. When values are equal, either consume both now or safely skip the duplicate later.
03Keep the result distinct
Append a candidate only when it differs from the last value already added.
How to think before coding
Before choosing a data structure, use the given sorted order. Each pointer exposes its input’s smallest unread value; the smaller front must be the next candidate overall. Advance that pointer even when the candidate is a duplicate. Save a candidate only if it differs from the last saved value, and remember to drain the remaining input after one ends.
Brute force and the improvement
Insert both arrays into a balanced sorted set: O((n + m) log(n + m)) time and O(n + m) storage in the worst case. Concatenate, sort, and remove duplicates has the same time bound and needs a combined working collection. These approaches also support unsorted input, but merging uses the already sorted order with O(1) auxiliary state, excluding the returned list.
Intuition
The smallest unprocessed value must be at one of the two current pointers. Add that value when it differs from the last value in the result, then move the matching pointer.
Java solution
import java.util.ArrayList;
import java.util.List;
public static List<Integer> sortedUnion(int[] first, int[] second) {
// This list is required output storage, not a copy of the inputs.
List<Integer> union = new ArrayList<>();
int left = 0;
int right = 0;
while (left < first.length && right < second.length) {
int value;
// The smaller front value is the smallest unread value overall.
if (first[left] <= second[right]) {
value = first[left++];
} else {
value = second[right++];
}
addIfNew(union, value); // Read equal candidates twice but save them once.
}
// One input ended. Drain the other, still skipping duplicates.
while (left < first.length) {
addIfNew(union, first[left++]);
}
while (right < second.length) {
addIfNew(union, second[right++]);
}
return union;
}
private static void addIfNew(List<Integer> values, int value) {
// Sorted traversal makes equal candidates adjacent.
if (values.isEmpty() || values.get(values.size() - 1) != value) {
values.add(value);
}
}Dry run

Read the text transcript
For [1, 1, 3, 5] and [2, 3, 4], take the smaller front value each time.
| Candidate source | Value | Append? | Result |
|---|---|---|---|
| First | 1 | Yes, result empty | [1] |
| First | 1 | No, duplicate | [1] |
| Second | 2 | Yes | [1, 2] |
| First | 3 | Yes | [1, 2, 3] |
| Second | 3 | No, duplicate | [1, 2, 3] |
| Second | 4 | Yes | [1, 2, 3, 4] |
| First, after second ends | 5 | Yes | [1, 2, 3, 4, 5] |
Each step consumes one input value, so neither pointer can get stuck.
Complexity
Time is O(n + m). The result uses O(n + m) space in the worst case.
Common mistake
Using a set and sorting the result works, but it ignores the fact that both inputs are already sorted. The two pointer solution uses that information directly.
Practice next
Next lessonLongest Subarray with Sum KMove from pointer state to prefix history.