Intersection Of Three Sorted Arrays Problem
Description
LeetCode Problem 1213.
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:
1
2
3
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.
Example 2:
1
2
Input: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]
Output: []
Solution
Hash Table Approach
A straightforward approach is to use a hash table. We can use a hash table to count the frequencies of each element in arr1, arr2, and arr3. Then we put the number that appear exactly 3 times to the result array. This is feasible because all of the three arrays are strictly increasing, so the elements will appear at most 3 times in all arrays.
The time complexity is O(n), and the space complexity is O(n).
Three Pointer Approach
We can leverage the fact that the three arrays are strictly increasing to reduce the space complexity.
We can use three pointers p1, p2, and p3 to iterate through arr1, arr2, and arr3. During the iteration, we increment the pointer that points to the smallest number (min(arr1[p1], arr2[p2], arr3[p3]) forward. If the numbers pointed to by p1, p2, and p3 are the same, we should put that number to the result array and move all three pointers forward.
The time complexity is O(n), and the space complexity is O(1).
Sample C++ Code
This is a C++ solution using a hash table approach. The time complexity is O(n), and the space complexity is O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
unordered_map <int, int> ht;
vector<int> res;
for (int i = 0; i < arr1.size(); i++) {
ht[arr1[i]] = 1;
}
for (int i = 0; i < arr2.size(); i++) {
if (ht.find(arr2[i]) != ht.end()) {
ht[arr2[i]]++;
}
}
for (int i = 0; i < arr3.size(); i++) {
if (ht.find(arr3[i]) != ht.end()) {
ht[arr3[i]]++;
}
if (ht[arr3[i]] == 3) {
res.push_back(arr3[i]);
}
}
return res;
}
int main() {
vector<int> arr1 = {1,2,3,4,5};
vector<int> arr2 = {1,2,5,7,9};
vector<int> arr3 = {1,3,4,5,8};
vector<int> res = arraysIntersection(arr1, arr2, arr3);
for (int i = 0; i < res.size(); i ++)
cout << res[i] << " " << endl;
return 0;
}
This is a C++ solution using a three pointer approach. The time complexity is O(n), and the space complexity is O(1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
vector<int> res;
int p1 = 0, p2 = 0, p3 = 0;
while(p1 < arr1.size() && p2 < arr2.size() && p3 < arr3.size()) {
if ((arr1[p1] == arr2[p2]) && (arr1[p1] == arr3[p3])) {
res.push_back(arr1[p1]);
p1++; p2++; p3++;
continue;
}
if ((arr1[p1] <= arr2[p2]) && (arr1[p1] <= arr3[p3]))
p1++;
else if ((arr2[p2] <= arr1[p1]) && (arr2[p2] <= arr3[p3]))
p2++;
else if ((arr3[p3] <= arr2[p2]) && (arr3[p3] <= arr1[p1]))
p3++;
}
return res;
}
int main() {
vector<int> arr1 = {1,2,3,4,5};
vector<int> arr2 = {1,2,5,7,9};
vector<int> arr3 = {1,3,4,5,8};
vector<int> res = arraysIntersection(arr1, arr2, arr3);
for (int i = 0; i < res.size(); i ++)
cout << res[i] << " " << endl;
return 0;
}