Intersection of Three Sorted Arrays
Problem
Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.
arr1 = [1, 2, 3, 4, 5], arr2 = [1, 2, 5, 7, 9], arr3 = [1, 3, 4, 5, 8][1, 5]def arrays_intersection(arr1, arr2, arr3):
i = j = k = 0
res = []
while i < len(arr1) and j < len(arr2) and k < len(arr3):
if arr1[i] == arr2[j] == arr3[k]:
res.append(arr1[i])
i += 1; j += 1; k += 1
else:
m = max(arr1[i], arr2[j], arr3[k])
if arr1[i] < m: i += 1
if arr2[j] < m: j += 1
if arr3[k] < m: k += 1
return resfunction arraysIntersection(arr1, arr2, arr3) {
let i = 0, j = 0, k = 0;
const res = [];
while (i < arr1.length && j < arr2.length && k < arr3.length) {
if (arr1[i] === arr2[j] && arr2[j] === arr3[k]) {
res.push(arr1[i]);
i++; j++; k++;
} else {
const m = Math.max(arr1[i], arr2[j], arr3[k]);
if (arr1[i] < m) i++;
if (arr2[j] < m) j++;
if (arr3[k] < m) k++;
}
}
return res;
}class Solution {
public List<Integer> arraysIntersection(int[] a1, int[] a2, int[] a3) {
List<Integer> res = new ArrayList<>();
int i = 0, j = 0, k = 0;
while (i < a1.length && j < a2.length && k < a3.length) {
if (a1[i] == a2[j] && a2[j] == a3[k]) {
res.add(a1[i]);
i++; j++; k++;
} else {
int m = Math.max(a1[i], Math.max(a2[j], a3[k]));
if (a1[i] < m) i++;
if (a2[j] < m) j++;
if (a3[k] < m) k++;
}
}
return res;
}
}vector<int> arraysIntersection(vector<int>& a1, vector<int>& a2, vector<int>& a3) {
vector<int> res;
int i = 0, j = 0, k = 0;
while (i < (int)a1.size() && j < (int)a2.size() && k < (int)a3.size()) {
if (a1[i] == a2[j] && a2[j] == a3[k]) {
res.push_back(a1[i]);
i++; j++; k++;
} else {
int m = max(a1[i], max(a2[j], a3[k]));
if (a1[i] < m) i++;
if (a2[j] < m) j++;
if (a3[k] < m) k++;
}
}
return res;
}Explanation
Because all three arrays are already sorted, we can find common elements with a single sweep using three pointers i, j, k — one for each array — instead of building hash sets.
At every step we look at the three current values. If they are all equal, that number is in the intersection: we record it and advance all three pointers together.
If they are not all equal, the smallest value(s) can never catch up to the largest, so they are safe to skip. We compute m, the max of the three current values, and advance every pointer whose value is below m. This nudges the laggards forward without ever skipping a possible match.
The loop ends as soon as any pointer runs off the end of its array, since a common element must appear in all three.
Example: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]. All start at 1 — match, record 1. After several catch-up moves the pointers align again on 5 — match, record 5. The result is [1, 5]. Each pointer only moves forward, so the total work is the combined length of the arrays.