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;
}




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...

Uncommon Words From Two Sentences Problem

LeetCode 884. A sentence is a string of single-space separated...

Triples With Bitwise And Equal To Zero Problem

LeetCode 982. Given an integer array nums, return the number...