Given two sorted arrays arr1 and arr2, return their intersection — the set of values that appear in both arrays.
The result must contain no duplicates: even if a value repeats inside either array, it appears at most once in the answer. Return the common values in ascending order (the natural order you get by walking the sorted inputs).
If the arrays share nothing, return an empty array.
Input: arr1 = [1, 2, 3, 4], arr2 = [2, 4, 6, 7, 8] Output: [2, 4] 2 and 4 are the only values present in both arrays.
Input: arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 4, 6, 7, 8] Output: [2, 4] 2 and 4 are common; duplicates are collapsed to a single copy each.
Input: arr1 = [1, 2], arr2 = [3, 4] Output: [] The arrays share no values, so the intersection is empty.
- 1 <= arr1.size, arr2.size <= 10^5 - 1 <= arr1[i], arr2[i] <= 10^6 - arr1 is sorted in ascending order - arr2 is sorted in ascending order
Intersection is the twin of Union, and it drives home the same lesson: when both inputs are sorted, a two-pointer merge beats a hash set. This exact "sorted-merge-join" is how database engines intersect two indexes ordered by the same key — it's a genuinely production-grade pattern.
Given two ascending arrays arr1 and arr2, return the distinct values that appear in both, in ascending order. If they share nothing, return an empty array.
Worked example — arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 4, 6, 7]
1 < 2 → advance arr1 2 = 2 → match! record 2, advance both 2 = 2 → equals last recorded → skip, advance both 3 < 4 → advance arr1 4 = 4 → match! record 4, advance both result: [2, 4] ✓
“Are both arrays sorted?”
Yes — that's what makes the two-pointer walk correct. Unsorted inputs would push you to a hash set or a pre-sort.
“Can either array contain duplicates?”
Yes. So your logic must collapse repeats both within an array and across the two.
“How many times does a shared value appear in the output?”
Once. The intersection is a set of common values, even if 2 appears many times in both inputs.
“What if there are no common elements?”
Return an empty array — the loop simply exits without recording anything.
“What order should the result be in?”
Ascending. Walking both sorted arrays left to right produces exactly that order.
“How large can the arrays be?”
Up to 10^5 each. The two-pointer merge is O(n+m) time and O(1) extra space — no set to allocate.
A couple of questions.
Both arrays are sorted, and each can have duplicates?
Each shared value appears once in the output, in ascending order?
Since they're sorted, I'll two-pointer walk them and record a match once, advancing both on equality.
If arr1[i] < arr2[j], then arr1[i] is smaller than everything remaining in arr2 (which only grows), so it can't be a common value — discard it and advance i. This is what makes a single linear walk correct, and why the arrays must be sorted.
When the two pointers meet the same value, it's in the intersection. Record it, then move both pointers past it. Advancing only one would leave the twin to be matched again and duplicate the value.
Because a shared value can repeat in both arrays, guard each record with "is this the same as the value I last added?" That single check keeps the intersection a proper set without any extra structure.
| Scan every pair | Hash set | Two pointers | |
|---|---|---|---|
| Idea | Search each value of one in the other | Membership lookups | Merge walk, match on equal |
| Time | O(n·m) | O(n+m) | O(n+m) |
| Space | O(1) | O(m) | O(1) |
The full code for all three is in the Approaches selector below.
Key takeaway
For the intersection of two sorted arrays, walk them with two pointers: advance the pointer at the smaller value, and on equality record the value once and advance both. Guard against duplicates by comparing to the last recorded value. O(n+m) time, O(1) extra space — the sorted-merge-join databases use for ordered indexes.
