Common Elements in Three Sorted Arrays — Problem & Solution
Common Elements in Three Sorted Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Common Elements in Three Sorted Arrays is an easy coding problem on arrays and two pointers, asked in Amazon, Infosys and Oracle interviews.
- Difficulty: Easy
- Topics: Arrays, Two Pointers
- Asked at: Amazon, Infosys, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given three arrays a, b and c, each sorted in non-decreasing order, return the values that appear in all three.
The result must be sorted ascending and contain each value once, even if it repeats in the inputs. Return [] when nothing is common.
Example 1
Input: a = [1,5,10,20,40,80], b = [6,7,20,80,100], c = [3,4,15,20,30,70,80,120]
Output: [20,80]
Example 2
Input: a = [1,2,3], b = [4,5,6], c = [7,8,9]
Output: []
Example 3
Input: a = [1,1,2,2,3], b = [1,1,2,2,3], c = [1,2,2,3,3]
Output: [1,2,3]
Explanation: Duplicates collapse to one entry each.
Constraints
1 <= a.length, b.length, c.length <= 1000001 <= values <= 1000000Each array is sorted non-decreasing.
Hints for Common Elements in Three Sorted Arrays
Hint 1
Three pointers, one per array, all starting at 0.
Hint 2
If all three point at the same value, record it and advance all three.
Hint 3
Otherwise advance whichever pointer sits on the smallest value — it can never match anything later.
How to solve Common Elements in Three Sorted Arrays
Sorted inputs make a three-way merge possible: keep one pointer per array and always move the one that is behind, because a value smaller than another array's current value can never appear there again.
Approach
- Start
i,j,kat0and loop while all three are in range. - If
a[i] == b[j] == c[k], append the value unless it equals the last one recorded, then advance all three pointers. - Otherwise advance the pointer whose value is the smallest of the three.
Why it works
Each array is sorted, so if a[i] is strictly smallest it cannot equal anything at or after b[j] and c[k] — discarding it is safe. Every pointer only moves forward, so the scan is linear.
Complexity
- Time —
O(n + m + p) - Space —
O(1) beyond the output
Pitfalls
- Forgetting the duplicate guard —
[1,1]in all three arrays would report1twice. - Advancing all three pointers on a partial match loses values.
Reference solution
Python
from typing import List
def commonElements(a: List[int], b: List[int], c: List[int]) -> List[int]:
out = []
i = j = k = 0
while i < len(a) and j < len(b) and k < len(c):
if a[i] == b[j] == c[k]:
if not out or out[-1] != a[i]:
out.append(a[i])
i += 1
j += 1
k += 1
elif a[i] < b[j]:
i += 1
elif b[j] < c[k]:
j += 1
else:
k += 1
return outJava
public static int[] commonElements(int[] a, int[] b, int[] c) {
List<Integer> out = new ArrayList<>();
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length && k < c.length) {
if (a[i] == b[j] && b[j] == c[k]) {
if (out.isEmpty() || out.get(out.size() - 1) != a[i]) out.add(a[i]);
i++; j++; k++;
} else if (a[i] < b[j]) i++;
else if (b[j] < c[k]) j++;
else k++;
}
int[] res = new int[out.size()];
for (int t = 0; t < out.size(); t++) res[t] = out.get(t);
return res;
}C++
vector<int> commonElements(vector<int>& a, vector<int>& b, vector<int>& c) {
vector<int> out;
size_t i = 0, j = 0, k = 0;
while (i < a.size() && j < b.size() && k < c.size()) {
if (a[i] == b[j] && b[j] == c[k]) {
if (out.empty() || out.back() != a[i]) out.push_back(a[i]);
i++; j++; k++;
} else if (a[i] < b[j]) i++;
else if (b[j] < c[k]) j++;
else k++;
}
return out;
}JavaScript
var commonElements = function(a, b, c) {
var out = [];
var i = 0, j = 0, k = 0;
while (i < a.length && j < b.length && k < c.length) {
if (a[i] === b[j] && b[j] === c[k]) {
if (out.length === 0 || out[out.length - 1] !== a[i]) out.push(a[i]);
i++; j++; k++;
} else if (a[i] < b[j]) i++;
else if (b[j] < c[k]) j++;
else k++;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique