What it is
A hash set gives O(1) average-case membership testing, and a surprising number of problems that look like they need sorting or nested loops actually just need the question "have I seen this value (or this suffix, or this boundary) before?" answered quickly. Once you have a set of everything relevant, checking a candidate against it replaces an O(n) inner scan with O(1), turning an O(n²) brute force into O(n) overall. The set itself is usually trivial to build — the skill is recognizing which values belong in it and what question you're really asking against it.
When it applies
- You need to know whether a value repeats anywhere in a collection, with no need to know where.
- You're checking whether a contiguous run or boundary exists in an unordered collection (a consecutive integer sequence, valid string splits) where sorting would work but costs more than necessary.
- A recursive or dynamic-programming check needs a fast "is this substring/value a valid unit" test at every step, and precomputing that answer set avoids repeating string or value comparisons.
- Needing the position, count, or order of occurrences — not just whether something exists — means a hash set alone throws away information you need; reach for a hash map instead.
Tells in the problem
- "Does any value occur more than once" or "return True/False" about presence, with no requirement to report where.
- "Longest run of consecutive values" in an array with no guarantee of sorted order or a bounded range.
- "Can this string be split into pieces that are each in a dictionary" — reusable pieces checked against a fixed vocabulary.
- Large or unbounded value ranges that rule out an array-indexed lookup, pushing you toward a hash-based structure instead.
- A brute force that description as "for each element, check every other element" — the second loop is usually replaceable by a set lookup.
The classic mistake
Rebuilding or rescanning the set (or worse, the whole array) inside what should be an O(1) check, silently turning the intended O(n) solution back into O(n²) — in the consecutive-sequence problem this looks like starting a "count how long this run is" scan from every single element instead of only from elements that are confirmed run-starts (a value whose predecessor isn't in the set). The fix is to make the entry condition into the loop explicit and cheap to check (one set lookup) before doing any real work inside it, so each element is the start of a scan at most once across the whole run of the algorithm.
Questions to start with
- Contains Duplicate — the base case: build the set, check membership, nothing else.
- Longest Consecutive Sequence — the run-start trick that keeps membership checks from turning into repeated O(n) scans.
- Word Break — combines a hash set of valid words with dynamic programming, using set lookups to keep each substring check O(1).