Intersection of Two Arrays II

summary

• Given two integer arrays, return an array of their intersection
• Each element in the result must appear as many times as it shows in both arrays.

approach

• The approach used is to first count the occurrences of each element in the first array using an unordered map
• Then, for each element in the second array, if it exists in the map and its count is greater than 0, decrement the count and add the element to the result array.

complexity

• O(n + m) where n and m are the sizes of the input arrays

explain

• The solution iterates over the first array to count the occurrences of each element in the unordered map
• Then, it iterates over the second array to find elements that exist in the map and add them to the result array
• This approach ensures that each element in the result appears as many times as it shows in both arrays.

Solution Code:

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        vector answer;
        unordered_map cnt;
        for(int i = 0 ; i < nums1.size(); i++){
            cnt[nums1[i]]++;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            if(cnt[nums2[i]]){
                cnt[nums2[i]]--;
                answer.push_back(nums2[i]);
            }
        }
        return answer;
    }
};