Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

getIntersection doesn't work for arrays with repeated values #169

Closed
brooswajne opened this issue May 9, 2020 · 1 comment
Closed

getIntersection doesn't work for arrays with repeated values #169

brooswajne opened this issue May 9, 2020 · 1 comment

Comments

@brooswajne
Copy link

Since your check for an element being in the intersection is for it's count in the flattened array of arrays to be equal to the number of total arrays, this doesn't work correctly if one of the arrays has repeated values.

e.g. getIntersection([ 1, 1 ], [ 2, 3 ]) returns [ 1 ]

@brooswajne
Copy link
Author

brooswajne commented May 9, 2020

Something like this would work I believe

const getIntersect = (first, ...arrs) => [...arrs.reduce((insect, arr) => arr.reduce((next, elt) => insect.has(elt) ? next.add(elt) : next, new Set()), new Set(first))]

Not very pretty, but still actually shorter than the current solution. Haven't given it a huge amount of thought, but I think it should have slightly better time complexity (goes over each array once rather than twice, still effectively O(n), could be improved further but not sure how you'd do it in one line), just a shame that it creates a new Set each iteration rather than mutating the initial one... Not sure how you'd do that elegantly in one line though.

phuocng added a commit that referenced this issue Aug 11, 2020
generalise getIntersection, fixes #169
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant