1149. Intersection of Three Sorted Arrays

• Difficulty: Easy

• Topics: Hash Table, Two Pointers

• Similar Questions:

  • Intersection of Two 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.

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 <= 1000
• 1 <= arr1[i], arr2[i], arr3[i] <= 2000

Solutions:

class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> arr12 = helper(arr1, arr2);
        return helper(arr12, arr3);
    }

private: 
    vector<int> helper(vector<int>& arr1, vector<int>& arr2) {
        int i1 = 0, i2 = 0;
        vector<int> ret;
        while (i1 < arr1.size() && i2 < arr2.size()) {
            if (arr1[i1] == arr2[i2]) {
                ret.push_back(arr1[i1]);
                ++i1;
                ++i2;
            } else if (arr1[i1] < arr2[i2]) {
                ++i1;
            } else {
                ++i2;
            }
        }

        return ret;
    }

};