0
slow
Given n + 1 integers in [1, n], exactly one value is duplicated. Treat each value as a next pointer and the array becomes an implicit linked list with a cycle — Floyd's algorithm then finds the duplicate in O(n) time and O(1) space without modifying the array.
You have an array nums of length n + 1 where every integer is in [1, n]. Exactly one number is repeated (possibly more than twice). Return that duplicate without modifying the array and using only O(1) extra space.
Worked example: nums = [1, 3, 4, 2, 2] → 2. The value 2 appears at indices 3 and 4, and treating values as pointers causes a cycle: 0→1→3→2→4→2→4→….
f(i) = nums[i]. Start a walk at index 0 and follow 0 → nums[0] → nums[nums[0]] → …. Because values are in [1, n]the walk never leaves the array, and because one value is duplicated, two distinct indices point to the same "next" node — which is exactly a cycle whose entranceis the duplicate value. Floyd's two-pointer algorithm locates cycle entrances in O(n) time and O(1) space.slow and fast at index 0. At each step, slow = nums[slow] (1 hop) and fast = nums[nums[fast]] (2 hops).slow === fast. They are guaranteed to meet inside the cycle because fast laps slow.finder = 0. Advance both slow and finder one step at a time. When they meet, that index is the cycle entrance — and the cycle entrance index equals the duplicate value.return slow (or finder— they're equal).slow and fast at index 1 (the first value) instead of index 0. Index 0 is the "outside-the-cycle" node; values in [1, n] guarantee we can never cycle back to 0, so it is the correct head. Starting at 1may put you inside the cycle immediately and break Phase 2's distance argument.The binary search on value approach counts how many elements are ≤ midand runs in O(n log n) with O(1) space — a valid alternative when Floyd's feels non-obvious. A bit-manipulation XORtrick works only when the duplicate appears exactly twice; Floyd's handles any number of repetitions.
x → f(x) as a sequence and need to find a repeat.[1, 3, 4, 2, 2]. Treat each value as a pointer: nums[i] is the "next" node from index i. Starting both slow and fast at index 0.1function findDuplicate(nums: number[]): number {2 // Phase 1 — find the intersection point inside the cycle.3 // Treat each value as a "next" pointer: nums[i] → nums[nums[i]].4▶ let slow = 0;5▶ let fast = 0;6 do {7 slow = nums[slow];8 fast = nums[nums[fast]];9 } while (slow !== fast);1011 // Phase 2 — find the entrance to the cycle (= the duplicate).12 // Reset one pointer to the start; both now move one step at a time.13 let finder = 0;14 while (slow !== finder) {15 slow = nums[slow];16 finder = nums[finder];17 }18 return slow; // entrance of cycle = duplicate value19}
function findDuplicate(nums: number[]): number {
// Phase 1 — find the intersection point inside the cycle.
// Treat each value as a "next" pointer: nums[i] → nums[nums[i]].
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// Phase 2 — find the entrance to the cycle (= the duplicate).
// Reset one pointer to the start; both now move one step at a time.
let finder = 0;
while (slow !== finder) {
slow = nums[slow];
finder = nums[finder];
}
return slow; // entrance of cycle = duplicate value
}0 is the "pre-cycle head"; values are in [1, n] so no value points back to 0.do…whileensures at least one iteration (both start equal at 0, but one step separates them). They must meet inside the cycle — Floyd's theorem guarantees it.nums[i]).λ + μ steps (cycle length + tail) and Phase 2 at most μ steps, both linear in n. O(1) space — only slow, fast, and finder.≤ mid; if the count exceeds mid the duplicate is in [1, mid]. O(n log n) / O(1) — useful when Floyd's feels like magic to the interviewer.μ + a·λ and fast μ + b·λ for integers a, b. Their difference is a multiple of λ. Resetting one pointer to 0 and advancing both one step means both reach the entrance after exactly μ more steps.function findDuplicate(nums: number[]): number {
// Phase 1 — find the intersection point inside the cycle.
// Treat each value as a "next" pointer: nums[i] → nums[nums[i]].
let slow = 0;
let fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// Phase 2 — find the entrance to the cycle (= the duplicate).
// Reset one pointer to the start; both now move one step at a time.
let finder = 0;
while (slow !== finder) {
slow = nums[slow];
finder = nums[finder];
}
return slow; // entrance of cycle = duplicate value
}λ + μ steps (cycle length + tail) and Phase 2 at most μ steps, both linear in n. O(1) space — only slow, fast, and finder.For each element, scan the rest of the array for an equal value. It honours the read-only and O(1)-space constraints — it just trades away speed.
function findDuplicate(nums: number[]): number {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) return nums[i]; // found the repeat
}
}
return -1; // unreachable given the problem's guarantee
}O(n²) pairs, which times out for the large nthe problem allows. Floyd's cycle detection keeps the same O(1) space and read-only array while dropping the time to O(n).| n+1 integers all in [1, n], find duplicate | Floyd's cycle detection |
| read-only array, O(1) space constraint | two-pointer implicit linked list |
| find where a sequence of f(x) repeats | slow ×1 / fast ×2, then reset |
| "Linked List Cycle II" shape | phase 1 meet, phase 2 entrance |
let slow = 0, fast = 0;
// Phase 1: find meeting point
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow !== fast);
// Phase 2: find cycle entrance
let finder = 0;
while (slow !== finder) {
slow = nums[slow];
finder = nums[finder];
}
return slow;f(i) = nums[i]. Walking 0 → nums[0] → nums[nums[0]] → … forms a sequence; the duplicate value is pointed to by two different indices, creating a cycle.nums = [1, 3, 4, 2, 2]. What does findDuplicate return?if (seen.has(n)) return n; seen.add(n);. What is the main drawback vs. Floyd's?