DEV Community

loading...

Discussion on: And then the interviewer asks, "Can you do this with less code?"

Collapse
michaelsolati profile image
Michael Solati Author • Edited

So the first method is Θ(n log(n)), Mozilla and Google's implementations are a Merge Sort and Timsort respectively.

As for the the ECMA standard for a Set, internally they're recommended to use hash tables (or something similar). Insertion in hash tables run at Θ(1), so an array of n elements would reasonably be Θ(n).

Collapse
polmonroig profile image
Pol Monroig Company

Well yes, but worst case of hash tables is linear. If you don't mind the space you can create an auxiliar array and mark the positions. This is the "same" idea used in the hash table but it guarantees a O(n) solution. This solution requires O(n) extra space complexity, but hash table in worst case is also O(n) ( when all numbers are different)

Forem Open with the Forem app