AlgoDaily 01: Array Intersection
I’ve signed up to AlgoDaily as it seems like a fun way to get out some small blog posts on small coding tasks.
This is AlgoDaily Day 1: Array Intersection.
“Can you write a function that takes two inputs and returns their intersection? All element in the final result should be unique.”
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
intersection(nums1, nums2);
// [2]
“Here’s another one:”
const nums1 = [4, 9, 5];
const nums2 = [9, 4, 9, 8, 4];
intersection(nums1, nums2);
// [9, 4]
Here’s my first-thought naive implementation:
function intersection(setA, setB) {
return setA.reduce((intersected, x) => {
if (setB.includes(x) && !intersected.includes(x)) {
intersected.push(x);
}
return intersected;
}, []);
}
The idea is to filter setA to those that are also in setB, while also
ignoring duplicate items.
Testing it out:
intersection([1, 2, 2, 1], [2, 2]);
// Array [ 2 ]
intersection([4, 9, 5], [9, 4, 9, 8, 4]);
// Array [ 4, 9 ]
It might be more straightforward to just do a filter and then use a Set to
remove the duplicates:
function intersection(arrayA, arrayB) {
return [...new Set(setA.filter(x => setB.includes(x)))]
}
That does seem a lot cleaner.
Going through the test cases in AlgoDaily:
intersection([6, 0, 12, 10, 16], [3, 15, 18, 20, 15]);
// Array []
intersection([1, 5, 2, 12, 6], [13, 10, 9, 5, 8]);
// Array [ 5 ]
intersection([4, 17, 4, 4, 15, 16, 17, 6, 7], [15, 2, 6, 20, 17, 17, 8, 4, 5]);
// Array(4) [ 4, 17, 15, 6 ]
intersection([3], [15]);
// Array []
intersection([2, 16, 8, 9], [14, 15, 2, 20]);
// Array [ 2 ]
It turns out that AlgoDaily‘s suggested solution is very similar to the
version using Set().