1213. Intersection of Three Sorted Arrays
Tags: ‘Hash Table’, ‘Two Pointers’
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.
Example 1:
Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] Output: [1,5] Explanation: Only 1 and 5 appeared in the three arrays.
Constraints:
1 <= arr1.length, arr2.length, arr3.length <= 10001 <= arr1[i], arr2[i], arr3[i] <= 2000
Solution
Naive solution using hashmap to record occurance
O(X+Y+Z) O(length of intersection)
public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
// using hashmap traverse all three. O(X+Y+Z) O(length of intersection)
Map<Integer, Integer> map = new HashMap<>();
List<Integer> result = new LinkedList<>();
for (int i: arr1) {
map.put(i, 1);
}
for (int i: arr2) {
if (map.containsKey(i)) {
map.put(i, map.get(i) + 1);
}
}
for (int i: arr3) {
if (map.containsKey(i) && map.get(i) == 2) {
result.add(i);
}
}
return result;
}
Three Pointer, increment min pointer O(X+Y+Z) O(1 excluding result list)
public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
List<Integer> list = new ArrayList();
int p1 = 0, p2 = 0, p3 = 0;
while (p1 < arr1.length && p2 < arr2.length && p3 < arr3.length) {
int min = Math.min(arr1[p1], Math.min(arr2[p2], arr3[p3]));
if (arr1[p1] == arr2[p2] && arr1[p1] == arr3[p3]) list.add(arr1[p1]);
if (arr1[p1] == min) p1++;
if (arr2[p2] == min) p2++;
if (arr3[p3] == min) p3++;
}
return list;
}