Contains Duplicate
Hash-set membership scan
time O(n)space O(n)
Sorting would work but costs O(n log n). A hash set answers 'have I seen this value?' in O(1), so one left-to-right pass suffices: check each value against the set BEFORE adding it — the instant a lookup hits, a repeat exists and we can stop early.
Details
Animated on: Given an integer array, return true if any value appears at least twice, otherwise false.
Problem:Contains DuplicateEasy
Pattern:Hashing and Frequency Maps
Hash-set membership scan
step 1 / 9
7
[0]12
[1]4
[2]19
[3]15
[4]23
[5]4
[6]11
[7]Seed an empty set 'seen'. Walk i left to right asking one question per cell: is this value already in the set? A hit means a duplicate.
- i=0· arr[0] = 7
Pseudocode
1FUNCTION containsDuplicate(nums):2 make an empty set of seen values3 FOR i from 0 to (length of nums) - 1:4 IF nums[i] is already in the set: RETURN true5 add nums[i] to the set6 RETURN false
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Seed an empty set 'seen'. Walk i left to right asking one question per cell: is this value already in the set? A hit means a duplicate.
- seen is empty, so 7 is brand-new — add it. seen = {7}. Green cells below are exactly what the set remembers.
- Is 12 in {7}? No — safe. Add it: seen = {7, 12}.
- Is 4 in {7, 12}? No — safe. Add it: seen = {7, 12, 4}. Remember this 4 at index 2 — it matters soon.
- Is 19 in {7, 12, 4}? No — safe. Add it: seen = {7, 12, 4, 19}.
- Is 15 in {7, 12, 4, 19}? No — safe. Add it: seen = {7, 12, 4, 19, 15}.
- Is 23 in the set of six? No — safe. Add it: seen = {7, 12, 4, 19, 15, 23}.
- nums[6] = 4 — and 4 IS in seen (parked back at index 2). First repeat found: return true immediately, never even touching index 7.
- Answer: true — the value 4 appears at indices 2 and 6. One pass, early exit the moment the second 4 arrived.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.