3 ms·
If the language has a set data structure available, intersect all 3 sets. If it doesn't, sort all three arrays and iteratively go past the smallest value in eac
by wyager 10y ago
If the language has a set data structure available, intersect all 3 sets. If it doesn't, sort all three arrays and iteratively go past the smallest value in each array until you arrive at the same value in each array.
- thebradbain 10y agoWouldn't that have O(n*logn) time at worst: sorting [O(nlogn)] + traversal [O(n)] ? If space complexity is not a requirement, wouldn't it be better to iterate over each list and keep track of the occurrences of a digit in a dictionary (whichever keys have 3 occurrences are thus shared)? That way you could get the value in O(n) time. Or is there something I'm missing?
- mook 10y agoIterating each list is at least O(n) (because you just visited each item). So your dictionary building is in itself O(nlogn). As a minor optimization, when you walk the last list you can build the final list incrementally (check for things with two existing visits).