Loading…

easyBasicsSometimes asked

Find a Duplicate

Basics · 6 min

Given an integer array nums that contains at least one repeated value, return any value that appears more than once.

In plain English

Remember what you've seen in a hash set; the first value already in the set is a duplicate.

Examples

Example 1

Input: nums = [1, 3, 2, 3, 4]
Output: 3
Note: 3 repeats.

Example 2

Input: nums = [5, 5]
Output: 5
Note: 5 repeats.

Example 3

Input: nums = [1, 2, 2, 1]
Output: 2 or 1
Note: Either repeated value is valid.

Constraints

2 ≤ nums.length ≤ 10^5
At least one duplicate exists

Clarifying questions2First question: Are values bounded (e.g. 1..n)?Explore questions

Q1.Are values bounded (e.g. 1..n)?
If so I can do it in O(1) space; otherwise a set is the clean O(n) answer.
Q2.Return any duplicate or the first?
I return the first repeat encountered.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Walk the array adding each value to a hash set; the first value that's already present is a duplicate. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a hash set to trade space for time, with correct ordering.

Where candidates slip

O(n²) pair comparison, or add-before-check.

How to stand out

Offer the O(1)-space variants when values are bounded to 1..n (sign marking / Floyd).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Hash set seen

TimeO(n)SpaceO(n)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What data structure answers 'seen this before?' in O(1)?

2Hint 2Explore hint

Add elements to a set; the first failed insert is your duplicate.

3Hint 3Explore hint

Check membership before inserting, not after.

A · Core idea

Use a hash set as a memory of what you've already seen. Walk the array; the first element that is already in the set is a duplicate. O(n) time, O(n) space.

Why a set. A set answers 'have I seen this value before?' in O(1) average time. That converts the O(n²) brute force (compare every pair) into a single linear pass — you trade O(n) memory for the speedup.

Check-then-add ordering. You must test membership before inserting; insert first and the value is always 'present', so you'd never detect the repeat. In Java the idiom if (!seen.add(x)) return x; is neat because add returns false when the element already existed.

Constrained variants. If values are guaranteed in 1..n, you can find a duplicate in O(1) space using index-sign marking or Floyd's cycle detection — good things to mention, since the set solution uses extra memory.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 3, 2, 3, 4]

not in set

State{1}

Final result3

C · Code with teaching comments

solution.javaJava

Hash set seen — optimal

1 teaching note

1
public int findDuplicate(int[] nums) {
2
    java.util.Set<Integer> seen = new java.util.HashSet<>();
3
    for (int x : nums) {
4
        // Set.add returns false when the value was already present — that's the
5
        // duplicate.
6
        if (!seen.add(x)) return x;
7
    }
8
    return -1;
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Mention the O(n²) nested-loop brute force first, then the O(n) set — the trade is time for O(n) space.

ComplexityO(n) time, O(n) space — each element does an O(1) set lookup/insert, so O(n) time; the set can hold up to n values, so O(n) space.

E · Edge cases and pitfalls4nums = [5, 5] — Immediate repeat → 5.Explore edge cases

Edge cases handled

nums = [5, 5]Immediate repeat → 5.
nums = [1, 2, 2, 1]Returns the first repeat encountered (2).

Pitfalls

Nested loops (O(n²)) when a set gives O(n).
Inserting before checking, so the repeat is never detected.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int findDuplicate(int[] nums) { java.util.Set<Integer> seen = new java.util.HashSet<>(); for (int x : nums) { if (!seen.add(x)) return x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Add before checking

If you insert the value first, the membership test always succeeds and no duplicate is ever reported.

Explore the code comparison

Don't write this

for x in nums:
    seen.add(x)
    if x in seen: return x   # always true

Write this instead

for x in nums:
    if x in seen: return x
    seen.add(x)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash set membership

Code pattern to memorize

seen=set(); for x: if x in seen: return x; seen.add(x)

Rules to remember

1Add as you go.
2Already-present ⟹ duplicate.
3O(n) time, O(n) space.

Use this pattern when

Detecting repeats
'Have I seen this?' membership

Choose another pattern when

Values bounded to 1..n and O(1) space required — use sign marking

Interview takeaway

'Seen before?' questions are a hash set in disguise.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Hash set membership. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Contains Duplicate
Coming soon
Return just true/false using the same set.
Find the Duplicate Number (O(1) space)
Coming soon
Floyd's cycle detection when values are in 1..n.

Same pattern

easyBasicsSometimes asked

Find a Duplicate

Basics · 6 min

Given an integer array nums that contains at least one repeated value, return any value that appears more than once.

In plain English

Remember what you've seen in a hash set; the first value already in the set is a duplicate.

Examples

Example 1

Input: nums = [1, 3, 2, 3, 4]
Output: 3
Note: 3 repeats.

Example 2

Input: nums = [5, 5]
Output: 5
Note: 5 repeats.

Example 3

Input: nums = [1, 2, 2, 1]
Output: 2 or 1
Note: Either repeated value is valid.

Constraints

2 ≤ nums.length ≤ 10^5
At least one duplicate exists

Clarifying questions2First question: Are values bounded (e.g. 1..n)?Explore questions

Q1.Are values bounded (e.g. 1..n)?
If so I can do it in O(1) space; otherwise a set is the clean O(n) answer.
Q2.Return any duplicate or the first?
I return the first repeat encountered.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Walk the array adding each value to a hash set; the first value that's already present is a duplicate. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a hash set to trade space for time, with correct ordering.

Where candidates slip

O(n²) pair comparison, or add-before-check.

How to stand out

Offer the O(1)-space variants when values are bounded to 1..n (sign marking / Floyd).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Hash set seen

TimeO(n)SpaceO(n)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What data structure answers 'seen this before?' in O(1)?

2Hint 2Explore hint

Add elements to a set; the first failed insert is your duplicate.

3Hint 3Explore hint

Check membership before inserting, not after.

A · Core idea

Use a hash set as a memory of what you've already seen. Walk the array; the first element that is already in the set is a duplicate. O(n) time, O(n) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 3, 2, 3, 4]

not in set

State{1}

Final result3

C · Code with teaching comments

solution.javaJava

Hash set seen — optimal

1 teaching note

1
public int findDuplicate(int[] nums) {
2
    java.util.Set<Integer> seen = new java.util.HashSet<>();
3
    for (int x : nums) {
4
        // Set.add returns false when the value was already present — that's the
5
        // duplicate.
6
        if (!seen.add(x)) return x;
7
    }
8
    return -1;
9
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.9 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Mention the O(n²) nested-loop brute force first, then the O(n) set — the trade is time for O(n) space.

ComplexityO(n) time, O(n) space — each element does an O(1) set lookup/insert, so O(n) time; the set can hold up to n values, so O(n) space.

E · Edge cases and pitfalls4nums = [5, 5] — Immediate repeat → 5.Explore edge cases

Edge cases handled

nums = [5, 5]Immediate repeat → 5.
nums = [1, 2, 2, 1]Returns the first repeat encountered (2).

Pitfalls

Nested loops (O(n²)) when a set gives O(n).
Inserting before checking, so the repeat is never detected.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int findDuplicate(int[] nums) { java.util.Set<Integer> seen = new java.util.HashSet<>(); for (int x : nums) { if (!seen.add(x)) return x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Add before checking

If you insert the value first, the membership test always succeeds and no duplicate is ever reported.

Explore the code comparison

Don't write this

for x in nums:
    seen.add(x)
    if x in seen: return x   # always true

Write this instead

for x in nums:
    if x in seen: return x
    seen.add(x)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash set membership

Code pattern to memorize

seen=set(); for x: if x in seen: return x; seen.add(x)

Rules to remember

1Add as you go.
2Already-present ⟹ duplicate.
3O(n) time, O(n) space.

Use this pattern when

Detecting repeats
'Have I seen this?' membership

Choose another pattern when

Values bounded to 1..n and O(1) space required — use sign marking

Interview takeaway

'Seen before?' questions are a hash set in disguise.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Hash set membership. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Contains Duplicate
Coming soon
Return just true/false using the same set.
Find the Duplicate Number (O(1) space)
Coming soon
Floyd's cycle detection when values are in 1..n.

Same pattern