349. Intersection of Two Arrays

349. Intersection of Two Arrays (Easy)

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

 

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Companies:
Amazon, Facebook, Bloomberg, Apple, LinkedIn, VMware

Related Topics:
Array, Hash Table, Two Pointers, Binary Search, Sorting

Similar Questions:

• Intersection of Two Arrays II (Easy)
• Intersection of Three Sorted Arrays (Easy)

Solution 1. Hash Set

// OJ: https://leetcode.com/problems/intersection-of-two-arrays/
// Author: github.com/lzl124631x
// Time: O(A + B)
// Space: O(A + B)
class Solution {
public:
    vector<int> intersection(vector<int>& A, vector<int>& B) {
        unordered_set<int> a(begin(A), end(A)), b(begin(B), end(B));
        vector<int> ans;
        for (int n : a) {
            if (b.count(n)) ans.push_back(n);
        }
        return ans;
    }
};

Solution 2. Sort + Two Pointers

If both arrays are already sorted, this algorithm would just take O(A + B) time.

// OJ: https://leetcode.com/problems/intersection-of-two-arrays/
// Author: github.com/lzl124631x
// Time: O(AlogA + BlogB)
// Space: O(1)
class Solution {
public:
    vector<int> intersection(vector<int>& A, vector<int>& B) {
        sort(begin(A), end(A));
        sort(begin(B), end(B));
        vector<int> ans;
        int i = 0, j = 0, M = A.size(), N = B.size();
        while (i < M && j < N) {
            if (A[i] < B[j]) ++i;
            else if (A[i] > B[j]) ++j;
            else {
                int n = A[i];
                while (i < M && A[i] == n) ++i;
                while (j < N && B[j] == n) ++j;
                ans.push_back(n);
            }
        }
        return ans;
    }
};