Find the Duplicate Number — DSA Visualizer

Problem

Given an array of integers nums containing n+1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums; return this repeated number. You must solve the problem without modifying the array and use only constant extra space.

Example 1

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

Output: 2

Explanation: 2 appears twice.

Example 2

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

Output: 3

Explanation: 3 appears twice.

Constraints: 1 ≤ n ≤ 10⁵ | nums.length == n+1 | Only one repeated number exists

Array — Pointer Visualization

Phase 1 nums[i] = value treated as next index pointer

Variables

slow

—

fast

—

phase

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Treat nums[i]=j as edge i→j: duplicate creates a cycle

Phase 1: fast (2 steps) and slow (1 step) meet inside cycle

Phase 2: reset slow to nums[0], advance both 1 step

They meet at the cycle entrance = duplicate value

Time

O(n)

Space

O(1)

Why It Works

nums has values 1..n in n+1 slots. Treating value as next-pointer creates a linked list with a cycle at the duplicate. The duplicate value is pointed to by two different indices, so it is the cycle entrance. Floyd's algorithm finds the cycle start in O(n) time and O(1) space — Phase 1 brings both pointers inside the cycle; Phase 2 (reset slow to start, advance both at same speed) guarantees they meet exactly at the cycle entrance.