Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return true if any value appears at least twice. The interview-grade answer is a single pass building a hash set: if the current value is already in the set, return true; otherwise add it. O(n) time, O(n) space. The sort-and-scan alternative is O(n log n) time but O(1) extra space — name it as the space-saving trade-off.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for a hash set to trade space for time on a membership problem — and whether you can articulate the sort-based O(1)-space alternative.
Where candidates slip
Adding to the set before checking (so the first occurrence falsely matches itself), or using a heavyweight hash map when a set is enough.
How to stand out
State both solutions and their trade-off out loud: hash set is O(n)/O(n), sort-and-scan is O(n log n)/O(1). Ask whether memory or speed is the priority before committing.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAny duplicate in the array?Is O(1) extra space required?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Compare Every Pair
1Hint 1Explore hintHide hint
How would you check, with no extra data structures, whether two positions hold the same value?
2Hint 2Explore hintHide hint
Compare every pair (i, j) with j > i and return true the moment nums[i] == nums[j].
3Hint 3Explore hintHide hint
Two nested loops. It works but it's quadratic — that's your cue to look for a faster membership test.
A · Core idea
Check every unordered pair of indices: for each i, walk every later j > i and test nums[i] == nums[j]. Return true on the first match, false if no pair ever matches.
Why mention it at all. It's the literal reading of 'does any value appear twice', and stating it shows you can establish a correctness baseline before optimizing. But with n up to 10⁵, n²/2 ≈ 5 × 10⁹ comparisons would time out — so this is a stepping stone, not the submission.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3, 1]i=0, j=1
1 == 2?
notrueC · Code with teaching comments
Reference implementation previewpublic boolean containsDuplicate(int[] nums) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { return true;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Starting j at i + 1 avoids comparing an element with itself and avoids re-checking the same pair in reverse. The quadratic cost comes from re-scanning; a hash set removes the re-scan by remembering what we've already seen.
ComplexityO(n²) time, O(1) space — n(n−1)/2 comparisons in the worst case (all distinct), no extra memory.
E · Edge cases and pitfalls2Starting j at 0 — compares an element with itself and reports a false duplicate.Explore edge casesHide edge cases
Pitfalls
- Starting j at 0 — compares an element with itself and reports a false duplicate.
- Forgetting the final return false when no pair matches.
Approach 2 of 2 · Optimal
Hash Set — One Pass (Optimal)
1Hint 1Explore hintHide hint
What data structure answers 'have I seen this exact value already?' in O(1) average time?
2Hint 2Explore hintHide hint
Scan left to right. Keep a set of values seen so far; for each value, check the set before adding.
3Hint 3Explore hintHide hint
If the value is already in the set you've found a duplicate — return true. Otherwise add it and continue.
A · Core idea
Maintain a hash set of values encountered so far. Walk the array once; for each value x, if x is already in the set, a duplicate exists so return true. Otherwise insert x and continue. If the loop finishes, every value was distinct, so return false.
The shift from brute force. Brute force re-scans the array for every element (quadratic). The set lets us replace 'scan everything before me' with a single O(1) membership query, because the set already remembers everything before the current index. We pay O(n) memory to make each check constant time.
Why check before insert. If we inserted x first and then checked membership, every element would find itself in the set and we'd return true immediately — even on a fully distinct array. The lookup must run against the set as it existed before this element.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3, 1]Hash-map state
x=1
1Continue scanning
add 1
trueC · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
This is the minimal form of the 'remember what you've seen' trade that powers Two Sum and Longest Consecutive Sequence. A set (not a map) is the right tool because we only need presence — no associated value or count.
ComplexityO(n) time, O(n) space — One pass × O(1) average set operations = O(n) time. The set holds up to n elements → O(n) space.
E · Edge cases and pitfalls5nums = [1] — Single element can't repeat — loop adds 1, finishes, returns false.Explore edge casesHide edge cases
Edge cases handled
nums = [1]Single element can't repeat — loop adds 1, finishes, returns false.nums = [-1, -1]Negatives hash fine; second -1 is found in the set → true.
Pitfalls
- Inserting before checking — every element matches itself, always returns true.
- Using a HashMap with dummy values where a HashSet is clearer and lighter.
- Forgetting that sorting (the O(1)-space alternative) mutates the input — clone if the caller needs order preserved.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) { if (!seen.add(num)) { return true;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Insert-before-check (false positive)
If you add the element first, the very next membership test finds it, so even a fully distinct array reports a duplicate.
Explore the code comparisonHide the code comparison
Insert-before-check (false positive)
If you add the element first, the very next membership test finds it, so even a fully distinct array reports a duplicate.
Don't write this
for num in nums:
seen.add(num)
if num in seen:
return TrueWrite this instead
for num in nums:
if num in seen:
return True
seen.add(num)2Sorting without copying when order matters
The O(1)-space variant sorts in place, which destroys the caller's array ordering. Sort a copy if the original must be preserved.
Explore the code comparisonHide the code comparison
Sorting without copying when order matters
The O(1)-space variant sorts in place, which destroys the caller's array ordering. Sort a copy if the original must be preserved.
Don't write this
Arrays.sort(nums); // mutates caller's array
for (int i = 1; i < nums.length; i++)
if (nums[i] == nums[i - 1]) return true;Write this instead
int[] copy = nums.clone();
Arrays.sort(copy);
for (int i = 1; i < copy.length; i++)
if (copy[i] == copy[i - 1]) return true;Revise
Carry the pattern into the interview
Pattern to remember
Membership testing via hash set
Code pattern to memorize
seen = set()
for x in nums:
if x in seen: return True
seen.add(x)
return FalseRules to remember
- 1Check membership before adding — otherwise every element 'matches itself'.
- 2A set, not a map — you only need presence, not a value or a count.
- 3Return early on the first repeat; don't scan the whole array if you don't have to.
- 4If asked to do it in
O(1)space, pivot to sort then compare adjacent (O(n log n)). - 5
len(set(nums)) != len(nums)is the one-liner — fine to mention, but show the loop to prove you know the mechanics.
Use this pattern when
- 'Has any value been seen before?' over an unsorted array
- Need a fast O(1) presence test while streaming through data
- De-duplication, uniqueness checks, or first-repeat detection
Choose another pattern when
- Strict O(1) extra space required → sort then compare neighbours
- Need the index/positions of the duplicate → use a hash map (value → index)
- Need *counts* of each value → hash map, not a set
Interview takeaway
Whenever the question is 'have I seen this before?', a hash set turns the answer into an O(1) lookup. It's the simplest member of the same family as Two Sum, Longest Consecutive Sequence, and Group Anagrams.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternHash Set membership testing. Reach for it whenever the question reduces to 'have I seen this value before?' on unsorted data. Same family as Two Sum, Longest Consecutive Sequence, and Valid Anagram.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Contains Duplicate IIDuplicate within distance k — slide a window of a hash set of size k.
- Contains Duplicate IIIComing soonValues within t and indices within k — bucketing or a balanced BST window.
- Two SumSame hash-based 'have I seen the partner?' idea, but storing value → index.