3 ms·
Wouldn'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
by thebradbain 10y ago
Wouldn'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).