All patterns
Hashing
Arrays & Strings
Beginner
Interactive
Trade memory for constant-time membership checks.
Time
O(n) average
Space
O(n)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
A hash set remembers values already encountered. This trace finds the first duplicate by checking membership before inserting each value, replacing a nested comparison with one linear pass.
Analogy
A hands-on model of hashing that exposes every state change instead of hiding it inside a library call.
When to reach for it
- Learning the underlying data structure.
- Tracing state changes and invariants.
- Building a reusable interview template.
Language-independent template
seen = set()
for value in nums:
if value in seen: return value
seen.add(value)Complexity — time O(n) average, space O(n).
Common mistakes
- Skipping boundary checks.
- Updating state in the wrong order.
- Using the structure without preserving its invariant.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Contains DuplicateLC 217
Determine whether any value appears at least twice.
Medium
Find the longest consecutive run in an unsorted array.
Hard
Find the smallest absent positive integer using constant extra space.
Variations
Change the input and replay the trace.
Adapt the operation to a related interview problem.