Find the Duplicate Number

TWO POINTERS · MEDIUM

Builds on Day 4: Two-Pointer Pattern

The optimal solution below is the classic two-pointer “tortoise and hare” technique applied to an array instead of a linked list; read that lesson first if tracking two pointers moving at different speeds is still a new idea.

The problem

You’re given an array nums with n + 1 integers, where every value is in the range [1, n] inclusive. Exactly one number is repeated — it might show up twice, or many more times than that — and every other number appears exactly once. Find the repeated number. For example, [1,3,4,2,2] has n = 4 and five elements; 2 is the one that repeats, so the answer is 2. Likewise [3,1,3,4,2] returns 3.

The catch that makes this problem interesting: you’re asked to do it without modifying the input array and using only O(1) extra space. A Set or a frequency map solves this trivially, but neither meets that bar — the real solution has to be cleverer than “just remember what you’ve seen.”

Solution 1: Brute force — hash set of seen values

The direct approach: walk the array once, and for every value, check whether it’s already in a Set. The first value that’s already there is the duplicate — return immediately, no need to keep scanning. This is completely correct and dead simple, but it’s honest to call it “brute force” here specifically because of what the problem actually demands: the Set is a second data structure that can grow as large as the input itself, which violates the O(1) extra space constraint outright.

nums = [1, 3, 4, 2, 2] — Set grows with each new value; early exit when 2 repeats at index 4

Press play to scan the array with a Set tracker.

seen set: —

Step 0 / 0

▶ Play — O(n) time↺ Reset

The code

function findDuplicateBruteForce(nums) {
  const seen = new Set();
  for (const v of nums) {
    if (seen.has(v)) return v;
    seen.add(v);
  }
  return -1; // unreachable — the problem guarantees a duplicate exists
}

Line by line:

• seen is a Set — every distinct value gets added exactly once, and membership checks (has) are the whole algorithm.
• if (seen.has(v)) return v; — this is the entire “detection” logic. The moment a value shows up that’s already in the Set, it must be the duplicate (the problem guarantees there’s only one repeated value), so the function returns immediately instead of finishing the scan.
• seen.add(v) only runs for values that weren’t already there — by the time this line executes, v is guaranteed new.
• The final return -1 is unreachable for any input satisfying the problem’s guarantee; it exists only as a defined fallback.

Complexity

Time	Space	Approach
O(n)	O(n)	Hash set of seen values, early exit on first repeat

Solution 2: Optimal — Floyd’s Cycle Detection (tortoise and hare)

The trick is a reframing: since every value in nums is guaranteed to be in [1, n], and there are n + 1 indices (0 through n), every value nums[i] is ALWAYS itself a valid index back into the same array. That means you can treat the array as an implicit linked list: index i “points to” index nums[i]. Because one value is duplicated, at least two different indices point to that same target — which means this implicit list is guaranteed to have a cycle, and the value at the cycle’s entrance is exactly the duplicate.

Phase 1 — detect the cycle. Run the standard tortoise-and-hare: a slow pointer advances one step per iteration (slow = nums[slow]), a fast pointer advances two (fast = nums[nums[fast]]). Because the implicit list has a cycle, fast can never “escape” past slow without lapping it — they’re guaranteed to land on the same index eventually. That meeting point proves a cycle exists, but it is not necessarily the duplicate value itself — it’s just some node inside the cycle.

Phase 2 — find the entrance. Reset one pointer back to index 0 (the start), keep the other at wherever they met, and now advance both by exactly one step per iteration. They will meet again — and this second meeting point IS the cycle’s entrance, which is the duplicate. Why resetting to the start works is the genuinely non-obvious part: if the tail (from index 0 to the cycle’s entrance) has length L, and the cycle has length C, the math of how far slow and fast traveled in phase 1 guarantees that walking L more steps from both the meeting point and from index 0 lands on the exact same index — the entrance. No array copy, no Set, no modification — just two index variables.

nums = [1, 2, 3, 4, 5, 6, 4] — implicit graph: index i → index nums[i]. Tail is 0→1→2→3, cycle is 4→5→6→4. Duplicate is 4.

Press play to run Floyd's two-phase cycle detection.

phase: — · pointers: —

Step 0 / 0

▶ Play — O(n) time↺ Reset

The code

function findDuplicateOptimal(nums) {
  let slow = nums[0];
  let fast = nums[nums[0]];

  // Phase 1: advance slow by 1 step, fast by 2 steps, until they meet.
  // Guaranteed to happen because the implicit linked list has a cycle.
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[nums[fast]];
  }

  // Phase 2: reset one pointer to the start. Move both by 1 step at a
  // time — they meet again exactly at the cycle's entrance, which IS
  // the duplicate value.
  let slow2 = 0;
  while (slow2 !== fast) {
    slow2 = nums[slow2];
    fast = nums[fast];
  }

  return fast;
}

Line by line:

• slow = nums[0]; fast = nums[nums[0]]; — both pointers take their first hop(s) before the loop condition is even checked, so the while loop’s exit condition (slow === fast) can be evaluated immediately rather than trivially being true at index 0 for both.
• Phase 1’s loop is the classic tortoise-and-hare: slow moves one hop, fast moves two. Because a cycle is guaranteed to exist, fast re-enters the cycle and eventually laps slow from behind — they can’t miss each other forever.
• let slow2 = 0; — phase 2 introduces a fresh pointer starting at index 0, deliberately reusing the variable name pattern (not renaming fast) so it’s clear fast keeps its position from wherever phase 1 left it.
• Phase 2’s loop moves both pointers one step per iteration — this is the part that finds the cycle’s entrance, not just any point inside the cycle.
• return fast; — after phase 2’s loop exits, fast (and slow2) are on the same index: the entrance, i.e. the duplicate.

Complexity

Time	Space	Approach
O(n)	O(1)	Floyd’s Cycle Detection — two-phase tortoise and hare

Complexity comparison

Solution	Time	Space
Brute force (hash set)	O(n)	O(n)
Optimal (Floyd’s Cycle Detection)	O(n)	O(1)

Both solutions are O(n) time — there is no asymptotic speedup here, and it would be dishonest to claim one. The real, honest improvement Floyd’s offers is space: it drops the O(n) Set down to O(1), two index variables that don’t grow with the input — which is exactly what the problem’s actual constraint (no extra space, don’t modify the array) is asking for.

Interview corner

Why is it valid to treat nums as an implicit linked list where index i points to index nums[i]? What specifically makes that safe here?

• It’s only safe because every value in nums is guaranteed to be in [1, n], and the array has n + 1 valid indices (0 through n) — so nums[i] is always itself a usable index back into the same array. Nothing ever “points off the end.”
• Values are constrained to start at 1, not 0 — that means no value ever points back to index 0, which is exactly why index 0 always sits on the tail, never inside the cycle. That’s a structural guarantee the algorithm quietly relies on.
• If values could fall outside [1, n], nums[nums[i]] could read past the array’s bounds (returning undefined) or point at index 0 in a way that breaks the tail/cycle shape — the entire “walk it like a linked list” framing only holds because the input range is constrained exactly this way.

What is the actual, honest complexity improvement of Floyd’s Cycle Detection over the Set-based brute force — and what would be dishonest to claim?

• Both solutions are O(n) TIME — one pass over the array either way (phase 1 and phase 2 together still add up to a bounded number of hops). Claiming Floyd’s is “faster” in the Big-O sense would be incorrect.
• The real difference is SPACE: the Set is O(n) because it can grow to hold one entry per distinct value, while Floyd’s is O(1) — just slow, fast, and slow2, regardless of how large nums is.
• That space difference is not just a nice-to-have here — it’s literally what the problem asks for. The brute force is a correct solution to a different, easier problem (find a duplicate, any way you like) than the one actually being asked (find it in O(1) extra space, without modifying the array).

Phase 1 finds a meeting point inside the cycle. Why isn’t that meeting point itself the answer — and why does resetting one pointer to the start in phase 2 find the actual entrance?

• Phase 1’s meeting point only proves a cycle exists — fast could have lapped slow from anywhere inside the cycle, not necessarily right at the entrance. Tracing nums=[1,2,3,4,5,6,4], phase 1 meets at index 6, but the real duplicate is 4 — a completely different node.
• The reset works because of a distance relationship: if the tail (index 0 to the entrance) has length L and the cycle has length C, the amount fast outpaced slow by during phase 1 is always a multiple of C. That fact guarantees walking exactly L more steps from index 0, and from the phase-1 meeting point, both land on the entrance at the same time.
• It’s a genuinely non-obvious result — most people’s first instinct is that the meeting point IS the answer. Being able to explain why it isn’t (and why the reset step fixes that) is usually the actual signal an interviewer is listening for, more than just reciting the two-phase steps from memory.

Common follow-up

“What if you don’t reset to 0 — could you instead keep counting hops from the phase-1 meeting point and stop after exactly one full lap of the cycle?” That would tell you the cycle’s LENGTH, not its entrance — a related but different piece of information, and not what this problem is asking for.

Trick question — this problem’s values are always integers in [1, n], so NaN can never actually appear in nums. But suppose the same “seen tracker” pattern from the brute force were reused on an array that COULD contain NaN — would Array.prototype.indexOf and Set.prototype.has both still catch a repeated NaN?

console.log([NaN].indexOf(NaN));      // ?
console.log([NaN].includes(NaN));     // ?
console.log(new Set([NaN]).has(NaN)); // ?

• Answer: -1, then true, then true — not three matching results.
• indexOf compares with strict equality (===), and NaN === NaN is famously false — so indexOf can NEVER find a NaN, even one that’s really there. An indexOf-based duplicate check would silently miss it.
• Array.prototype.includes and Set.prototype.has both use SameValueZero comparison instead, which treats NaN as equal to itself — so both correctly detect it. That’s exactly why the brute-force solution above uses seen.has(v), not an indexOf-style check.

Trap

This is also why Set.has() is the right tool for the brute force beyond just this NaN semantics point — it’s O(1) average lookup versus Array.prototype.includes’ O(n) linear scan, which matters once the seen collection grows large. Verified directly: checking membership 50 times against a 200,000-element collection took about 0.002ms total with a Set versus roughly 1.9ms with Array.includes on this machine — a difference that only gets more dramatic as the input grows, since one is O(1) and the other is O(n) per check.

Quiz

Quiz: 1. Why is it valid to treat nums as an implicit linked list where index i points to index nums[i]?

Because every value is guaranteed to be in [1,n], so nums[i] is always itself a valid index into the array

Every value in nums is guaranteed to be in [1,n], and there are n+1 valid indices (0 through n) — so nums[i] is always itself a usable index back into the same array, which is exactly what makes the “index points to index” framing safe.

Quiz: 2. What is the real, honest complexity improvement of Floyd’s Cycle Detection over the Set-based brute force?

Space only — both are O(n) time, but space drops from O(n) to O(1)

Both solutions are O(n) time — one pass over the array either way. The real, honest improvement Floyd’s offers is space: O(n) for the Set down to O(1) for a couple of index variables — which is exactly what the problem’s real constraint asks for.

Quiz: 3. What does the meeting point found at the end of phase 1 (slow === fast) actually tell you?

Only that a cycle exists — it’s not necessarily the duplicate value itself

The phase-1 meeting point only proves a cycle exists somewhere in the implicit list — fast could have lapped slow from any point inside the cycle, not necessarily the entrance. Phase 2 is what actually locates the entrance (the duplicate).

Quiz: 4. In phase 2, what does resetting a pointer to index 0 and moving both pointers one step at a time actually locate?

The cycle’s entrance — which is the duplicate value

Resetting one pointer to index 0 and stepping both pointers by exactly one hop per iteration is what finds the cycle’s entrance specifically — a distance relationship guarantees both pointers reach the entrance at the same time.

Quiz: 5. Which membership check can NEVER find a repeated NaN value, even when one genuinely exists in the collection?

Array.prototype.indexOf — it uses strict equality, and NaN === NaN is false

Array.prototype.indexOf uses strict equality (===), and NaN === NaN is false — so indexOf can never find a NaN, even a real one. Array.prototype.includes and Set.prototype.has both use SameValueZero comparison instead, which correctly treats NaN as equal to itself.