Link: https://leetcode.com/problems/intersection-of-two-arrays-ii/
Solution:

- iterate through nums1, count the occurrence of each element and save the results in a map
- iterate through nums2 and add to the output the elements that exists in the map
- at the same time, once an element has been found in the map, decrease the occurrence count so we can add to the output the same element as many times as appears in both lists.
var intersect = function(nums1, nums2) {
var map = {};
var output = [];
for (var i = 0; i < nums1.length; i++)
{
var current = map[nums1[i]];
map[nums1[i]] = current == undefined? 1 : current + 1;
}
for (var j = 0; j < nums2.length; j++)
{
var current = map[nums2[j]];
if (current != undefined && current > 0)
{
map[nums2[j]] = current - 1;
output.push(nums2[j]);
}
}
return output;
};
Complexity: O(n)
Leave a Reply