Loading…

mediumArraysAsked very often

Find the Duplicate Number

Q: How do you solve Find the Duplicate Number using the Hash Set (Baseline) approach?

When to use it: Offer it first as the obvious O(n)-time idea, then note it violates the O(1)-space rule and pivot. Scan the array, inserting each value into a hash set. The moment you try to insert a value that's already there, that value is the duplicate. **Why it's the natural first answer.** 'Find the repeated element' screams 'remember what you've seen', and a hash set gives O(1) membership. It's correct, simple, and a good baseline to state. **Why it fails the constraints.** The problem explicitly caps extra space at O(1), and the set grows to O(n). So while the time is optimal, the space disqualifies it. Mentioning it shows you know the easy route and understand precisely which rule rules it out — a better signal than pretending the constraint isn't there. **The bridge to the real answer.** To drop the space to O(1) without mutating the array, you need structure already present in the data. The clue is the value range `[1, n]`: every element is itself a valid index, which means the array can be *read* as a linked list — and detecting a repeat becomes detecting a cycle, which Floyd's does in O(1) space. Time complexity: O(n). Space complexity: O(n).

Two Pointers · 29 of 30 · 9 min

Given an array nums of n + 1 integers where each value is in the range [1, n], there is exactly one repeated number. Return that repeated number.

You must not modify the array and must use only constant extra space, in better than O(n²) time.

In plain English

Because n+1 values are drawn from {1..n}, the pigeonhole principle guarantees a repeat. Reading nums[i] as 'next pointer from node i' turns the array into a linked list with a cycle, and the duplicate is precisely where the cycle begins.

Examples

Example 1

Input: nums = [1, 3, 4, 2, 2]
Output: 2
Note: 2 appears twice. Following indices 0→1→3→2→4→2→4… cycles at 2.

Example 2

Input: nums = [3, 1, 3, 4, 2]
Output: 3
Note: 3 is repeated; the implicit linked list's cycle entrance is 3.

Example 3

Input: nums = [2, 2, 2, 2, 2]
Output: 2
Note: Duplicate appearing many times — still resolves to 2.

Constraints

1 ≤ n ≤ 10⁵, nums.length == n + 1
1 ≤ nums[i] ≤ n (every value is a valid index into nums)
Exactly one value is duplicated; it may appear more than twice
Read-only array; O(1) extra space

Clarifying questions4First question: Can I modify the array or use extra space?Explore questions

Q1.Can I modify the array or use extra space?
The constraints say no to both. That rules out sorting and a hash set and points to the Floyd's-on-the-array approach.
Q2.Could the duplicate appear more than twice?
Yes. Floyd's still works — multiple occurrences just mean multiple edges into the cycle entrance, which is still the answer.
Q3.Are all values guaranteed in [1, n]?
Yes — that's what makes nums[i] always a legal index and the linked-list framing valid. If values could be 0 or out of range, this breaks.
Q4.Do you want the value or an index?
The duplicated value. The cycle entrance node's identifier is exactly that value.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Treat the array as a linked list where index i points to nums[i]. Because values are in [1, n] and there are n+1 of them, a duplicate creates a cycle. Run Floyd's tortoise-and-hare to find the cycle, then the cycle entrance is the duplicate — O(n) time, O(1) space, and the array is left unmodified.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can reframe a bounded-value array as a linked list and apply Floyd's two-phase cycle detection to hit O(1) space without mutating the input.

Where candidates slip

Reaching for a hash set or sort (violating the no-extra-space / no-modify constraints), or running only phase 1 and returning the meeting point instead of the cycle entrance.

How to stand out

Explain why a cycle must exist (pigeonhole on values in [1, n]), then derive why phase 2 lands exactly on the entrance — the algebra of the distances, not hand-waving.

Choose

Compare the available approaches

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

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set (Baseline)	`O(n)`	`O(n)`	Offer it first as the obvious O(n)-time idea, then note it violates the O(1)-space rule and pivot.	Read
2	Floyd's Cycle Detection on the Array (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want under the no-modify, O(1)-space constraints. Frame the array as a linked list first.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind the duplicateExtra space allowed?YesNoExplore the full tree

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 2

Hash Set (Baseline)

TimeO(n)SpaceO(n)

Offer it first as the obvious O(n)-time idea, then note it violates the O(1)-space rule and pivot.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the simplest way to detect the first value you've already seen?

2Hint 2Explore hint

Walk the array, adding each value to a set; the first value already present is the duplicate.

3Hint 3Explore hint

This is O(n) time but O(n) space — and the problem forbids extra space. How could you detect a repeat without storing seen values?

A · Core idea

Scan the array, inserting each value into a hash set. The moment you try to insert a value that's already there, that value is the duplicate.

Why it's the natural first answer. 'Find the repeated element' screams 'remember what you've seen', and a hash set gives O(1) membership. It's correct, simple, and a good baseline to state.

Why it fails the constraints. The problem explicitly caps extra space at O(1), and the set grows to O(n). So while the time is optimal, the space disqualifies it. Mentioning it shows you know the easy route and understand precisely which rule rules it out — a better signal than pretending the constraint isn't there.

The bridge to the real answer. To drop the space to O(1) without mutating the array, you need structure already present in the data. The clue is the value range [1, n]: every element is itself a valid index, which means the array can be read as a linked list — and detecting a repeat becomes detecting a cycle, which Floyd's does in O(1) space.

B · Visual dry run

Interactive dry run

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

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

Hash-map state

insert 2 (first)

lookup 2

ValueIndex / state

1→ ✓

3→ ✓

4→ ✓

2→ ✓

Continue scanning

2 not present → add

Final result2

C · Code with teaching comments

Reference implementation previewpublic int findDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int x : nums) { if (!seen.add(x)) { // add returns false if already present return x;Explore the full code

solution.javaJava

Hash Set (Baseline) — reference

2 teaching notes

1
public int findDuplicate(int[] nums) {
2
    Set<Integer> seen = new HashSet<>();
3
    for (int x : nums) {
4
        if (!seen.add(x)) {   // add returns false if already present
5
            // Returns the value, not an index.
6
            return x;
7
        }
8
    }
9
    return -1;                // unreachable given the guarantee
10
}

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

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

The hash set trades space for simplicity. When an interviewer forbids that space, look for exploitable structure in the input — here, values being valid indices is the door to the pointer-chasing solution.

ComplexityO(n) time, O(n) space — One pass with O(1) average set operations → O(n) time. The set can hold up to n values → O(n) space, which the constraints disallow.

E · Edge cases and pitfalls3Using O(n) space when the problem forbids it.Explore edge cases

Pitfalls

Using O(n) space when the problem forbids it.
Returning the index instead of the value.
Assuming it generalizes when values aren't in [1, n] — it does, but the optimal doesn't.

03.2

Approach 2 of 2 · Optimal

Floyd's Cycle Detection on the Array (Optimal)

TimeO(n)SpaceO(1)

The answer they want under the no-modify, O(1)-space constraints. Frame the array as a linked list first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Read nums[i] as 'the next index to jump to from i'. Since every value is in [1, n], that's always a valid jump. What shape does following the jumps trace out?

2Hint 2Explore hint

Because two indices share the same value (the duplicate), two arrows point into the same node — that creates a cycle. Finding the duplicate becomes finding the cycle's entrance.

3Hint 3Explore hint

Phase 1: tortoise (one step) and hare (two steps) until they meet inside the cycle. Phase 2: reset one pointer to nums[0], advance both one step at a time; they meet at the cycle entrance, which is the duplicate.

A · Core idea

Reinterpret the array as a function f(i) = nums[i], i.e. a linked list where node i links to node nums[i]. Then run Floyd's two-phase cycle detection; the cycle's entrance node is the duplicated value.

Why a cycle must exist. There are n + 1 slots but values only range over {1, …, n}, so by the pigeonhole principle some value repeats. In the linked-list view, a repeated value means two different nodes both link to the same node — two arrows converging. Following links forward from index 0 can therefore never escape to infinity; it must eventually revisit a node, i.e. loop. The starting index 0 is not part of the cycle (nothing points to it as a target since values are ≥ 1 and we begin there), so it sits on the 'tail' leading into the loop — exactly the linked-list-with-a-cycle shape Floyd's was designed for.

Phase 1 — find a meeting point. Move slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]). Inside a cycle the fast pointer gains one position on the slow pointer each iteration, so it eventually laps and lands on it. When slow == fast, you're guaranteed to be somewhere inside the cycle — but not necessarily at its entrance.

Phase 2 — why resetting finds the entrance. Let a be the distance from the start to the cycle entrance, b the distance from the entrance to the meeting point, and c the rest of the cycle (so the cycle length is b + c). When they meet, slow has walked a + b and fast has walked a + b + k(b + c) for some integer k; since fast moved twice as far, 2(a + b) = a + b + k(b + c), which simplifies to a = (k−1)(b+c) + c. In words: the distance from the start to the entrance equals the distance from the meeting point to the entrance (modulo whole loops). So if you put one pointer back at nums[0] and advance both one step at a time, they collide exactly at the entrance — the duplicate.

Why this beats the alternatives. It's O(n) time like the hash set but O(1) space, and unlike sorting it never touches the array. That precise combination — fast, constant space, read-only — is why interviewers pose this problem: it filters for candidates who can see the hidden linked-list structure rather than reach for the default tools.

Why duplicates-more-than-twice are fine. Extra occurrences just add more arrows into the cycle entrance; the entrance node is unchanged, so the algorithm still returns it.

B · Visual dry run

Interactive dry run

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

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

Interactive diagram

Array viewed as a linked list with a cycle

phase 1 start

Active call / nodeSupporting contextReturned stateNot active

Indices link via nums[i]; two arrows into node 2 form the cycle, whose entrance (2) is the duplicate.

Final result2

C · Code with teaching comments

solution.javaJava

Floyd's Cycle Detection on the Array (Optimal) — optimal

4 teaching notes

1
public int findDuplicate(int[] nums) {
2
    // Phase 1: find a meeting point inside the cycle
3
    int slow = nums[0];
4
    int fast = nums[nums[0]];
5
    while (slow != fast) {
6
        slow = nums[slow];
7
        fast = nums[nums[fast]];
8
    }
9
    // Phase 2: find the cycle entrance = the duplicate
10
    // Phase 2: reset one pointer to the start. The distance algebra makes both meet at
11
    // the entrance.
12
    slow = nums[0];
13
    while (slow != fast) {
14
        slow = nums[slow];
15
        fast = nums[fast];
16
    }
17
    return slow;
18
}

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

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

The entire trick is the reframe: a bounded-value array is a linked list, a duplicate is a cycle, and the duplicate value is the cycle entrance. Floyd's then gives O(1) space for free. The phase-2 reset working is a clean distance-algebra result, not magic — be ready to derive a = c (mod cycle).

ComplexityO(n) time, O(1) space — Phase 1 and phase 2 each traverse O(n) nodes before meeting (the pointers cover at most a constant multiple of the list length). No auxiliary storage beyond two index variables → O(1) space.

E · Edge cases and pitfalls7nums = [1, 1] — n=1, two slots both 1. Cycle is immediate; phase 2 returns 1.Explore edge cases

Edge cases handled

nums = [1, 1]n=1, two slots both 1. Cycle is immediate; phase 2 returns 1.
nums = [2, 2, 2, 2, 2]Duplicate appears 5 times; the cycle entrance is still 2.
nums = [3, 1, 3, 4, 2]Entrance node is 3; algorithm returns 3 without modifying the array.

Pitfalls

Returning the phase-1 meeting point instead of running phase 2 to the entrance.
Mis-stepping the hare: it must be nums[nums[fast]], a true double step.
Assuming index 0 can be inside the cycle — it's on the tail because values are ≥ 1.
Falling back to a set or sort and violating the stated constraints.

Practice

Try the solution yourself

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

Editable code previewpublic int findDuplicate(int[] nums) { // Phase 1: find a meeting point inside the cycle int slow = nums[0]; int fast = nums[nums[0]]; while (slow != fast) {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.

Stopping at the meeting point

Phase 1 only guarantees a node inside the cycle, not the entrance. You must run phase 2 (reset + equal-speed walk) to reach the duplicate.

Explore the code comparison

Don't write this

while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
return slow;   // meeting point, NOT the entrance

Write this instead

while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
slow = nums[0];
while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;

Fast pointer not double-stepping

The hare must advance twice per iteration (nums[nums[fast]]). Single-stepping makes both pointers identical and they never meaningfully meet inside the cycle.

Explore the code comparison

Don't write this

while slow != fast:
    slow = nums[slow]
    fast = nums[fast]    # only one step — no relative speed

Write this instead

while slow != fast:
    slow = nums[slow]
    fast = nums[nums[fast]]

Violating the constraints with a set

It's correct but uses O(n) space, which the problem forbids. Under the stated rules, Floyd's is the expected answer.

Explore the code comparison

Don't write this

seen = set()
for x in nums:
    if x in seen:
        return x
    seen.add(x)   # O(n) space — disallowed

Write this instead

slow = fast = nums[0]
# ... Floyd's two-phase cycle detection in O(1) space

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Array as implicit linked list + Floyd's cycle detection (tortoise & hare)

Code pattern to memorize

slow = fast = nums[0]
repeat: slow = nums[slow]; fast = nums[nums[fast]]  until slow == fast
slow2 = nums[0]
while slow2 != slow: slow = nums[slow]; slow2 = nums[slow2]
return slow

Rules to remember

1The mapping i → nums[i] is a valid linked list because every value is in [1, n], so it's always a legal index (never points out of bounds, never to index 0 from itself in a way that breaks the start).
2Start both pointers at nums[0] (or conceptually at index 0 then take one step). The duplicate is the entrance of the cycle, not just any node in it.
3Phase 1 finds a meeting point inside the cycle; Phase 2 resets one pointer to the start and walks both at speed 1 — they meet at the entrance. This is Floyd's, not random.
4This does not modify the array and uses O(1) space — that's the whole reason it beats the sort and the seen-set.
5It finds the duplicate value, not its index, and works even if the duplicate appears more than twice.

Use this pattern when

Values are confined to [1, n] with n+1 elements → a cycle is guaranteed
You're forbidden from modifying the array AND must use O(1) extra space
You recognize 'each element points to another index' as a linked-list traversal
Exactly one duplicated value (possibly repeated) is promised

Choose another pattern when

You're allowed O(n) extra space → a hash set is simpler and just as fast
You're allowed to sort / mutate → sort then scan adjacent, or index-marking, is easier to code
Values aren't bounded to [1, n] → the linked-list framing breaks; use hashing

Interview takeaway

The leap is seeing an array of bounded values as a linked list whose cycle entrance is the duplicate. Once you reframe it that way, Floyd's algorithm delivers O(n) time and O(1) space without touching the input — the exact constraint combo interviewers use to rule out the easy answers.

Continue

Transfer the pattern to another problem

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

Transferable patternFloyd's tortoise-and-hare applied to an array reinterpreted as a linked list. The transferable insight: when values are bounded to valid indices, i → nums[i] is a traversal, duplicates become cycles, and constant-space cycle detection replaces hashing. The phase-2 reset relies on the distance identity a ≡ c (mod cycle length).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Equilibrium Index

Continue · Next problem

Stock Span

mediumArraysAsked very often

Find the Duplicate Number

Two Pointers · 29 of 30 · 9 min

Given an array nums of n + 1 integers where each value is in the range [1, n], there is exactly one repeated number. Return that repeated number.

You must not modify the array and must use only constant extra space, in better than O(n²) time.

In plain English

Examples

Example 1

Input: nums = [1, 3, 4, 2, 2]
Output: 2
Note: 2 appears twice. Following indices 0→1→3→2→4→2→4… cycles at 2.

Example 2

Input: nums = [3, 1, 3, 4, 2]
Output: 3
Note: 3 is repeated; the implicit linked list's cycle entrance is 3.

Example 3

Input: nums = [2, 2, 2, 2, 2]
Output: 2
Note: Duplicate appearing many times — still resolves to 2.

Constraints

1 ≤ n ≤ 10⁵, nums.length == n + 1
1 ≤ nums[i] ≤ n (every value is a valid index into nums)
Exactly one value is duplicated; it may appear more than twice
Read-only array; O(1) extra space

Clarifying questions4First question: Can I modify the array or use extra space?Explore questions

Q1.Can I modify the array or use extra space?
The constraints say no to both. That rules out sorting and a hash set and points to the Floyd's-on-the-array approach.
Q2.Could the duplicate appear more than twice?
Yes. Floyd's still works — multiple occurrences just mean multiple edges into the cycle entrance, which is still the answer.
Q3.Are all values guaranteed in [1, n]?
Yes — that's what makes nums[i] always a legal index and the linked-list framing valid. If values could be 0 or out of range, this breaks.
Q4.Do you want the value or an index?
The duplicated value. The cycle entrance node's identifier is exactly that value.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can reframe a bounded-value array as a linked list and apply Floyd's two-phase cycle detection to hit O(1) space without mutating the input.

Where candidates slip

Reaching for a hash set or sort (violating the no-extra-space / no-modify constraints), or running only phase 1 and returning the meeting point instead of the cycle entrance.

How to stand out

Explain why a cycle must exist (pigeonhole on values in [1, n]), then derive why phase 2 lands exactly on the entrance — the algebra of the distances, not hand-waving.

Choose

Compare the available approaches

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

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Set (Baseline)	`O(n)`	`O(n)`	Offer it first as the obvious O(n)-time idea, then note it violates the O(1)-space rule and pivot.	Read
2	Floyd's Cycle Detection on the Array (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want under the no-modify, O(1)-space constraints. Frame the array as a linked list first.	Read

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 2

Hash Set (Baseline)

TimeO(n)SpaceO(n)

Offer it first as the obvious O(n)-time idea, then note it violates the O(1)-space rule and pivot.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the simplest way to detect the first value you've already seen?

2Hint 2Explore hint

Walk the array, adding each value to a set; the first value already present is the duplicate.

3Hint 3Explore hint

This is O(n) time but O(n) space — and the problem forbids extra space. How could you detect a repeat without storing seen values?

A · Core idea

Scan the array, inserting each value into a hash set. The moment you try to insert a value that's already there, that value is the duplicate.

Why it's the natural first answer. 'Find the repeated element' screams 'remember what you've seen', and a hash set gives O(1) membership. It's correct, simple, and a good baseline to state.

B · Visual dry run

Interactive dry run

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

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

Hash-map state

insert 2 (first)

lookup 2

ValueIndex / state

1→ ✓

3→ ✓

4→ ✓

2→ ✓

Continue scanning

2 not present → add

Final result2

C · Code with teaching comments

solution.javaJava

Hash Set (Baseline) — reference

2 teaching notes

1
public int findDuplicate(int[] nums) {
2
    Set<Integer> seen = new HashSet<>();
3
    for (int x : nums) {
4
        if (!seen.add(x)) {   // add returns false if already present
5
            // Returns the value, not an index.
6
            return x;
7
        }
8
    }
9
    return -1;                // unreachable given the guarantee
10
}

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

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

ComplexityO(n) time, O(n) space — One pass with O(1) average set operations → O(n) time. The set can hold up to n values → O(n) space, which the constraints disallow.

E · Edge cases and pitfalls3Using O(n) space when the problem forbids it.Explore edge cases

Pitfalls

Using O(n) space when the problem forbids it.
Returning the index instead of the value.
Assuming it generalizes when values aren't in [1, n] — it does, but the optimal doesn't.

03.2

Approach 2 of 2 · Optimal

Floyd's Cycle Detection on the Array (Optimal)

TimeO(n)SpaceO(1)

The answer they want under the no-modify, O(1)-space constraints. Frame the array as a linked list first.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Read nums[i] as 'the next index to jump to from i'. Since every value is in [1, n], that's always a valid jump. What shape does following the jumps trace out?

2Hint 2Explore hint

Because two indices share the same value (the duplicate), two arrows point into the same node — that creates a cycle. Finding the duplicate becomes finding the cycle's entrance.

3Hint 3Explore hint

A · Core idea

Why duplicates-more-than-twice are fine. Extra occurrences just add more arrows into the cycle entrance; the entrance node is unchanged, so the algorithm still returns it.

B · Visual dry run

Interactive dry run

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

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

Interactive diagram

Array viewed as a linked list with a cycle

phase 1 start

Active call / nodeSupporting contextReturned stateNot active

Indices link via nums[i]; two arrows into node 2 form the cycle, whose entrance (2) is the duplicate.

Final result2

C · Code with teaching comments

solution.javaJava

Floyd's Cycle Detection on the Array (Optimal) — optimal

4 teaching notes

1
public int findDuplicate(int[] nums) {
2
    // Phase 1: find a meeting point inside the cycle
3
    int slow = nums[0];
4
    int fast = nums[nums[0]];
5
    while (slow != fast) {
6
        slow = nums[slow];
7
        fast = nums[nums[fast]];
8
    }
9
    // Phase 2: find the cycle entrance = the duplicate
10
    // Phase 2: reset one pointer to the start. The distance algebra makes both meet at
11
    // the entrance.
12
    slow = nums[0];
13
    while (slow != fast) {
14
        slow = nums[slow];
15
        fast = nums[fast];
16
    }
17
    return slow;
18
}

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

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

E · Edge cases and pitfalls7nums = [1, 1] — n=1, two slots both 1. Cycle is immediate; phase 2 returns 1.Explore edge cases

Edge cases handled

nums = [1, 1]n=1, two slots both 1. Cycle is immediate; phase 2 returns 1.
nums = [2, 2, 2, 2, 2]Duplicate appears 5 times; the cycle entrance is still 2.
nums = [3, 1, 3, 4, 2]Entrance node is 3; algorithm returns 3 without modifying the array.

Pitfalls

Returning the phase-1 meeting point instead of running phase 2 to the entrance.
Mis-stepping the hare: it must be nums[nums[fast]], a true double step.
Assuming index 0 can be inside the cycle — it's on the tail because values are ≥ 1.
Falling back to a set or sort and violating the stated constraints.

Practice

Try the solution yourself

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

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.

Stopping at the meeting point

Phase 1 only guarantees a node inside the cycle, not the entrance. You must run phase 2 (reset + equal-speed walk) to reach the duplicate.

Explore the code comparison

Don't write this

while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
return slow;   // meeting point, NOT the entrance

Write this instead

while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
slow = nums[0];
while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;

Fast pointer not double-stepping

The hare must advance twice per iteration (nums[nums[fast]]). Single-stepping makes both pointers identical and they never meaningfully meet inside the cycle.

Explore the code comparison

Don't write this

while slow != fast:
    slow = nums[slow]
    fast = nums[fast]    # only one step — no relative speed

Write this instead

while slow != fast:
    slow = nums[slow]
    fast = nums[nums[fast]]

Violating the constraints with a set

It's correct but uses O(n) space, which the problem forbids. Under the stated rules, Floyd's is the expected answer.

Explore the code comparison

Don't write this

seen = set()
for x in nums:
    if x in seen:
        return x
    seen.add(x)   # O(n) space — disallowed

Write this instead

slow = fast = nums[0]
# ... Floyd's two-phase cycle detection in O(1) space

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Array as implicit linked list + Floyd's cycle detection (tortoise & hare)

Code pattern to memorize

slow = fast = nums[0]
repeat: slow = nums[slow]; fast = nums[nums[fast]]  until slow == fast
slow2 = nums[0]
while slow2 != slow: slow = nums[slow]; slow2 = nums[slow2]
return slow

Rules to remember

1The mapping i → nums[i] is a valid linked list because every value is in [1, n], so it's always a legal index (never points out of bounds, never to index 0 from itself in a way that breaks the start).
2Start both pointers at nums[0] (or conceptually at index 0 then take one step). The duplicate is the entrance of the cycle, not just any node in it.
3Phase 1 finds a meeting point inside the cycle; Phase 2 resets one pointer to the start and walks both at speed 1 — they meet at the entrance. This is Floyd's, not random.
4This does not modify the array and uses O(1) space — that's the whole reason it beats the sort and the seen-set.
5It finds the duplicate value, not its index, and works even if the duplicate appears more than twice.

Use this pattern when

Values are confined to [1, n] with n+1 elements → a cycle is guaranteed
You're forbidden from modifying the array AND must use O(1) extra space
You recognize 'each element points to another index' as a linked-list traversal
Exactly one duplicated value (possibly repeated) is promised

Choose another pattern when

You're allowed O(n) extra space → a hash set is simpler and just as fast
You're allowed to sort / mutate → sort then scan adjacent, or index-marking, is easier to code
Values aren't bounded to [1, n] → the linked-list framing breaks; use hashing

Interview takeaway

Continue

Transfer the pattern to another problem

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

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Equilibrium Index

Continue · Next problem

Stock Span