LeetCode 1213 - Intersection of Three Sorted Arrays
The problem gives us three integer arrays, arr1, arr2, and arr3. Each array is already sorted in strictly increasing order. Strictly increasing means there are no duplicate values inside the same array, and every next element is larger than the previous one.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, Binary Search, Counting
Solution
Problem Understanding
The problem gives us three integer arrays, arr1, arr2, and arr3. Each array is already sorted in strictly increasing order. Strictly increasing means there are no duplicate values inside the same array, and every next element is larger than the previous one.
Our task is to return a new sorted array that contains only the numbers that appear in all three arrays simultaneously. In other words, we are looking for the intersection of the three arrays.
For example, if a number exists in arr1 and arr2 but not in arr3, it should not appear in the result. A value is included only if it is present in every array.
The important details in the problem statement are:
- The arrays are already sorted.
- The arrays contain unique values internally because they are strictly increasing.
- The output must also remain sorted.
- The array lengths are at most 1000, so the input size is relatively small, but we should still aim for an efficient solution.
The sorted property is especially important because it allows us to avoid expensive repeated searches. Instead of comparing every element against every other element, we can move through the arrays in a coordinated way.
Several edge cases are important to think about:
- There may be no common elements at all, in which case we return an empty array.
- One or more arrays may contain only a single element.
- All three arrays could be identical.
- Common values may appear only near the end of the arrays.
- Because arrays are strictly increasing, we never need to worry about duplicate handling inside the same array.
These guarantees simplify the implementation considerably.
Approaches
Brute Force Approach
A straightforward solution is to check every element in one array against the other two arrays.
For each value in arr1, we can search for that value inside arr2 and arr3. If the value exists in both arrays, we add it to the result.
Since the arrays are sorted, a naive brute force implementation might still use linear searches for membership checks. That would produce three nested scans overall.
For example:
- Iterate through every value in
arr1 - For each value, scan
arr2 - If found, scan
arr3
This approach is correct because every candidate element is explicitly verified against all arrays. However, it performs unnecessary repeated comparisons.
If each array has length n, the time complexity becomes O(n^2) in practice, because each membership test may require a full scan.
Optimal Approach
The key observation is that all three arrays are already sorted.
When multiple sorted arrays need to be compared, a multi pointer technique becomes very effective. Instead of restarting searches repeatedly, we can move through the arrays only once.
We maintain three pointers:
iforarr1jforarr2kforarr3
At every step:
- If all three current values are equal, we found a common element.
- Otherwise, we advance the pointer pointing to the smallest value.
Why does this work?
Suppose the current values are:
arr1[i] = 2
arr2[j] = 5
arr3[k] = 7
Since the arrays are sorted, the value 2 can never match future values in the other arrays because all future values are even larger. Therefore, we safely move pointer i forward.
This guarantees that every pointer moves only forward and never backward, producing a linear time solution.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Repeatedly scans arrays for every element |
| Optimal | O(n) | O(1) | Uses three pointers on sorted arrays |
Algorithm Walkthrough
- Initialize three pointers,
i,j, andk, all starting at index0. These pointers track the current position in each array. - Create an empty result array that will store the common elements.
- Continue processing while all three pointers are still inside their respective arrays. The loop stops as soon as one array is exhausted because no further common elements can exist afterward.
- Compare the current values:
arr1[i]arr2[j]arr3[k]
- If all three values are equal, then this number exists in all arrays:
- Add it to the result
- Move all three pointers forward because this value has already been processed
- Otherwise, determine which current value is the smallest:
- If
arr1[i]is smallest, incrementi - Else if
arr2[j]is smallest, incrementj - Otherwise, increment
k
- The reason we move only the smallest pointer is that the smaller value cannot possibly appear later in the other arrays. Since arrays are sorted, future elements will only become larger.
- Continue until one pointer reaches the end of its array.
- Return the result array.
Why it works
The algorithm maintains the invariant that every value before the current pointers has already been fully processed and can never participate in a future match.
When the smallest value is advanced, no possible common element is skipped because the other arrays already contain larger values. Since pointers only move forward, every element is examined at most once, guaranteeing both correctness and efficiency.
Python Solution
from typing import List
class Solution:
def arraysIntersection(
self,
arr1: List[int],
arr2: List[int],
arr3: List[int]
) -> List[int]:
i = 0
j = 0
k = 0
result = []
while i < len(arr1) and j < len(arr2) and k < len(arr3):
if arr1[i] == arr2[j] == arr3[k]:
result.append(arr1[i])
i += 1
j += 1
k += 1
else:
minimum_value = min(arr1[i], arr2[j], arr3[k])
if arr1[i] == minimum_value:
i += 1
elif arr2[j] == minimum_value:
j += 1
else:
k += 1
return result
The implementation directly follows the three pointer algorithm.
We begin by initializing three indices, one for each array. These indices always point to the current candidate values being compared.
The while loop continues only while every pointer remains valid. Once any pointer reaches the end of its array, further intersections become impossible.
Inside the loop, the first condition checks whether all three values are equal. If they are, the value belongs in the intersection result, so we append it and advance all pointers.
If the values are not equal, we compute the minimum among the three current elements. The pointer corresponding to that minimum value is advanced. This works because sorted order guarantees that smaller values cannot reappear later.
The algorithm never revisits elements, which is why it achieves linear time complexity.
Go Solution
func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) []int {
i := 0
j := 0
k := 0
result := []int{}
for i < len(arr1) && j < len(arr2) && k < len(arr3) {
if arr1[i] == arr2[j] && arr2[j] == arr3[k] {
result = append(result, arr1[i])
i++
j++
k++
} else {
minimumValue := arr1[i]
if arr2[j] < minimumValue {
minimumValue = arr2[j]
}
if arr3[k] < minimumValue {
minimumValue = arr3[k]
}
if arr1[i] == minimumValue {
i++
} else if arr2[j] == minimumValue {
j++
} else {
k++
}
}
}
return result
}
The Go implementation is structurally identical to the Python solution.
One small difference is that Go does not provide a built in min() function for multiple integers in the same way Python does, so we compute the minimum manually.
The result is stored in a slice initialized as an empty slice. Returning an empty slice naturally handles cases where no intersection exists.
There are no integer overflow concerns because the constraints are very small, with values capped at 2000.
Worked Examples
Example 1
arr1 = [1,2,3,4,5]
arr2 = [1,2,5,7,9]
arr3 = [1,3,4,5,8]
Initial state:
| i | j | k | arr1[i] | arr2[j] | arr3[k] | Action |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | Match found, add 1 |
Result:
[1]
Move all pointers:
| i | j | k | arr1[i] | arr2[j] | arr3[k] | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 | 3 | Move smallest pointers |
2 is smallest, advance i and j separately through iterations.
| i | j | k | arr1[i] | arr2[j] | arr3[k] | Action |
|---|---|---|---|---|---|---|
| 2 | 2 | 1 | 3 | 5 | 3 | Move smallest |
| 3 | 2 | 2 | 4 | 5 | 4 | Move smallest |
| 4 | 2 | 3 | 5 | 5 | 5 | Match found, add 5 |
Final result:
[1,5]
Example 2
arr1 = [197,418,523,876,1356]
arr2 = [501,880,1593,1710,1870]
arr3 = [521,682,1337,1395,1764]
| i | j | k | Values | Action |
|---|---|---|---|---|
| 0 | 0 | 0 | 197, 501, 521 | Move i |
| 1 | 0 | 0 | 418, 501, 521 | Move i |
| 2 | 0 | 0 | 523, 501, 521 | Move j |
| 2 | 1 | 0 | 523, 880, 521 | Move k |
| 2 | 1 | 1 | 523, 880, 682 | Move i |
The process continues without ever finding equal values.
Final result:
[]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n1 + n2 + n3) | Each pointer moves forward at most once per element |
| Space | O(1) | Only pointer variables are used, excluding output |
The time complexity is linear because each pointer only advances forward and never moves backward. Every element across all arrays is visited at most once.
The auxiliary space complexity is constant because the algorithm only stores a few integer pointers. The output array itself is not counted toward auxiliary space complexity.
Test Cases
from typing import List
class Solution:
def arraysIntersection(
self,
arr1: List[int],
arr2: List[int],
arr3: List[int]
) -> List[int]:
i = 0
j = 0
k = 0
result = []
while i < len(arr1) and j < len(arr2) and k < len(arr3):
if arr1[i] == arr2[j] == arr3[k]:
result.append(arr1[i])
i += 1
j += 1
k += 1
else:
minimum_value = min(arr1[i], arr2[j], arr3[k])
if arr1[i] == minimum_value:
i += 1
elif arr2[j] == minimum_value:
j += 1
else:
k += 1
return result
solution = Solution()
assert solution.arraysIntersection(
[1,2,3,4,5],
[1,2,5,7,9],
[1,3,4,5,8]
) == [1,5] # Basic example with two common elements
assert solution.arraysIntersection(
[197,418,523,876,1356],
[501,880,1593,1710,1870],
[521,682,1337,1395,1764]
) == [] # No common elements
assert solution.arraysIntersection(
[1],
[1],
[1]
) == [1] # Single identical element
assert solution.arraysIntersection(
[1],
[2],
[3]
) == [] # Single element arrays with no match
assert solution.arraysIntersection(
[1,2,3],
[1,2,3],
[1,2,3]
) == [1,2,3] # All arrays identical
assert solution.arraysIntersection(
[1,5,10],
[2,5,12],
[3,5,15]
) == [5] # One common middle value
assert solution.arraysIntersection(
[1,2,1000],
[1000],
[500,1000]
) == [1000] # Match near array end
assert solution.arraysIntersection(
[1,3,5,7,9],
[3,5,7],
[2,3,5,7,10]
) == [3,5,7] # Multiple consecutive matches
| Test | Why |
|---|---|
Example with [1,5] result |
Validates normal intersection behavior |
| Example with empty result | Ensures algorithm handles no matches |
| Single identical elements | Tests smallest valid input |
| Single non matching elements | Tests minimal no intersection case |
| All arrays identical | Ensures every value is returned |
| One shared middle value | Tests isolated intersection |
| Match near end | Verifies pointer advancement correctness |
| Multiple consecutive matches | Tests repeated successful matches |
Edge Cases
One important edge case occurs when there are no common elements at all. A buggy implementation might continue scanning unnecessarily or accidentally include partial matches. The three pointer method handles this naturally because pointers keep advancing until one array is exhausted, at which point the loop terminates and returns an empty result.
Another important case is when arrays contain only one element each. Small inputs often expose off by one errors or incorrect loop conditions. Since the loop checks pointer bounds before every comparison, the implementation safely handles arrays of length one.
A third important edge case is when the common elements appear only near the end of the arrays. Some incorrect implementations may prematurely stop searching after many mismatches. This algorithm continues progressing systematically because the smallest pointer always advances until all possible matches are checked.
A fourth subtle case is when one array is much shorter than the others. Because the loop stops as soon as any pointer reaches the end, the implementation avoids unnecessary work and still guarantees correctness.