LEETCODE 349 what's the significance mp[x]=1;

Yash Sinha 0
Viewed 37

I am looking at LeetCode problem 349. Intersection of Two Arrays:

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.

I solved it using a brute force algorithm, but then I found this solution:

class Solution { 
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        map<int,int> mp;
        vector<int> ans;
        for(int x : nums1)
            mp[x]=1;
        
        for(int x: nums2)
            if(mp[x]==1)
                mp[x]++;
    
        for(auto x: mp)
            if(x.second>1)
                ans.push_back(x.first);
        return ans;
    }   
};

And now my question: What's the significance mp[x]=1; in that solution?

data-structures c++
1 Answers

mp is a (hash)map, so it stores unique keys and associated values.

In this case the idea is to use the values in both input arrays as keys in such a map, and to associate the value 1 with a key when that key occurs in nums1 and to associate the value 2 with a key when that key occurs in nums1 and nums2. So that is a kind of "counter".

So mp[x] = 1 registers the value x (found in nums1) as key in that map and associates value 1 to it, to indicate that this key was found in nums1.

In the second loop, the map is used to verify whether a value x in nums2 is present as key in the map with an associated count of 1. If so, then the associated value is increased with mp[x]++ (so now it is 2).

The final loop iterates all the keys in the map and when it finds that the associated value is greater than 1 (i.e. it is 2), then that key value belongs in the result.

trincot0
Related