Is a hash map always the right answer to "find the duplicate"?

Question

Most of the duplicate-detection problems here can be solved with a set in O(n) time and O(n) space, and that is what I reach for every time. Is there a case where that is the wrong instinct, or is it genuinely the answer?

Kenji Morita · Accepted Answer

It is a good default. It stops being the answer when the constraints say something about the input that you are not using.

Input is sorted — duplicates are adjacent, so one pass comparing neighbours is O(1) space.
n + 1 values in the range 1..n — Floyd's cycle detection finds the duplicate in O(1) space by treating the array as a linked list.
Input is enormous and lives on disk — neither fits in memory; you sort externally or use a Bloom filter and accept false positives.

The tell is a constraint that would be pointless if the intended answer were a hash set. "The array is sorted" or "values are in the range 1..n" is the problem telling you it wants something else.

That said — in an interview, say the hash-set solution first. It is correct, it is fast to state, and it buys you the time to notice the trick. Silence while you hunt for the clever answer reads as being stuck.

Inès Berger · Answer

"A constraint that would be pointless otherwise" is a useful thing to look for. I had been reading constraints as limits rather than as hints.