1213. Intersection of Three Sorted Arrays

1213. Intersection of Three Sorted Arrays (Easy)

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.

Example 2:

Input: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]
Output: []

 

Constraints:

• 1 <= arr1.length, arr2.length, arr3.length <= 1000
• 1 <= arr1[i], arr2[i], arr3[i] <= 2000

Companies:
Facebook

Related Topics:
Array, Hash Table, Binary Search, Counting

Similar Questions:

• Intersection of Two Arrays (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/intersection-of-three-sorted-arrays/
// Author: github.com/lzl124631x
// Time: O(A + B + C)
// Space: O(1)
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& A, vector<int>& B, vector<int>& C) {
        int i = 0, j = 0, k = 0, R = A.size(), S = B.size(), T = C.size();
        vector<int> ans;
        while (i < R && j < S && k < T) {
            int a = A[i], b = B[j], c = C[k];
            if (a == b && b == c) {
                ans.push_back(a);
                ++i, ++j, ++k;
            } else {
                int mx = max({ a, b, c });
                if (a < mx) ++i;
                if (b < mx) ++j;
                if (c < mx) ++k;
            }
        }
        return ans;
    }
};