3 ms·

A Set would be even better IMO

• bastawhiz 8y ago
  A set would still have n log n complexity, though, wouldn't it? At least if the set was a tree.
  • deathanatos 8y ago
    The comment you're replying to is replying to a comment about using a hash map; I read it as a suggestion to replace that with a hash set, which would be O(n) in time & space for the article's problem. (You don't need the "value" half of the hash map for this problem.)
  • Sean1708 8y ago
    Why would a set have to be a tree? In fact would expect trees to be the less common way to implement sets (I would expect hash tables to be more common).
  • leshow 8y ago
    A set could have many implementations, it could be a HashSet and still have O(1) update/access. I was just referring to how using a hash map in this situation you actually don't need the value parameter-- so the correct data structure here is a set, not a map.