Intersection of Two Arrays II
Easy · Two Pointers · Explanation and code example
Frequency-Limited Intersection
How it works
Count values from the smaller input, then scan the other input. A value is part of the intersection only while its remaining count is positive. Decrementing after each match gives each value the smaller of its two occurrence counts.
Steps
- Choose the smaller array for the frequency table.
- For each value in the other array, append it if a count remains.
- Decrement the matched count.
Complexity
- Time: O(n + m) expected with hashing.
- Space: O(min(n, m)) working space plus output.
Things to watch for
- Preserve duplicate matches up to the available frequency.
- A set alone loses multiplicities.
- The returned order is not prescribed.
Python code example
import collections
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 = collections.Counter(nums1)
for num in nums2:
if count[num] > 0:
ans.append(num)
count[num] -= 1
return ans
C++ code example
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 (const auto it = count.find(num);
it != count.cend() && it->second-- > 0)
ans.push_back(num);
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.