2248

2248. Intersection of Multiple Arrays (Easy)

nums nums[i] distinct the list of integers that are present in each array of nums sorted in ascending order

 

Example 1:

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= sum(nums[i].length) <= 1000
• 1 <= nums[i][j] <= 1000
• All the values of nums[i] are unique.

Companies: Bloomberg, Uber

Related Topics:
Array, Hash Table, Counting

Similar Questions:

• Intersection of Two Arrays (Easy)
• Intersection of Two Arrays II (Easy)
• Find Smallest Common Element in All Rows (Medium)
• Intersection of Three Sorted Arrays (Easy)
• Find the Difference of Two Arrays (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/intersection-of-multiple-arrays
// Author: github.com/lzl124631x
// Time: O(MNlogN)
// Space: O(N)
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& A) {
        for (auto &r : A) sort(begin(r), end(r));
        vector<int> ans = A[0];
        int len = ans.size();
        for (int i = 1; i < A.size(); ++i) {
            int j = 0, k = 0, p = 0, N = A[i].size();
            for (; j < len && k < N;) {
                if (ans[j] < A[i][k]) ++j;
                else if (ans[j] > A[i][k]) ++k;
                else ans[p++] = ans[j], ++j, ++k;
            }
            len = p;
        }
        ans.resize(len);
        return ans;
    }
};