## Approach 1: Hash Table

• Time:O(m + n)
• Space:O(\min(m, n))

## C++

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
return intersect(nums2, nums1);

vector<int> ans;
unordered_map<int, int> count;

for (const int num : nums1)
++count[num];

for (const int num : nums2)
if (count.count(num) && count[num]-- > 0)
ans.push_back(num);

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length)
return intersect(nums2, nums1);

List<Integer> ans = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();

for (final int num : nums1)
count.put(num, count.getOrDefault(num, 0) + 1);

for (final int num : nums2)
if (count.containsKey(num) && count.get(num) > 0) {
ans.add(num);
count.put(num, count.get(num) - 1);
}

return ans.stream().mapToInt(i -> i).toArray();
}
}
``````

## Python

``````class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums1) > len(nums2):
return self.intersect(nums2, nums1)

ans = []
count = Counter(nums1)

for num in nums2:
if count[num] > 0:
ans.append(num)
count[num] -= 1

return ans
``````

## Approach 2: Two Pointers

• Time:O(m\log m + n\log n)
• Space:O(\min(m, n))

## C++

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(begin(nums1), end(nums1));
sort(begin(nums2), end(nums2));
// What if the given array is already sorted?
// How would you optimize your algorithm?

vector<int> ans;
int i = 0;  // nums1's index
int j = 0;  // nums2's index

while (i < nums1.size() && j < nums2.size())
if (nums1[i] < nums2[j]) {
++i;
} else if (nums1[i] > nums2[j]) {
++j;
} else {
ans.push_back(nums1[i]);
++i;
++j;
}

return ans;
}
};
``````
• Time:O(\min(m\log n, n\log m))
• Space:O(\min(m, n))

## C++

``````class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
return intersect(nums2, nums1);

vector<int> ans;
int lowerBound = 0;  // lower bound for the binary search

sort(begin(nums1), end(nums1));
sort(begin(nums2), end(nums2));

for (const int num : nums1) {
const int i = binarySearch(nums2, lowerBound, num);
if (i < nums2.size() && nums2[i] == num) {
ans.push_back(num);
lowerBound = i + 1;
}
}

return ans;
}

private:
// perform binary search on the bigger array
// find the first index l s.t nums2[l] >= target
int binarySearch(vector<int>& nums2, int lo, int target) {
int l = lo;
int r = nums2.size();

while (l < r) {
const int m = (l + r) / 2;
if (nums2[m] >= target)
r = m;
else
l = m + 1;
}

return l;
}
};
``````