Find the Duplicate Number

01 Matrix

Return the one repeated value in a read-only array by treating it as a cycle-detection problem.

You are given an array `nums` containing `n + 1` integers where each value is in the range `[1, n]` inclusive. Exactly one integer value is duplicated; it may appear more than twice, but no second distinct value is duplicated. Return that repeated value.

You must solve the problem **without modifying the array** and using only **O(1) extra space**.

**Input / output**
- Input: `nums: int[]`
- Output: `int`

**Examples**
1. `nums = [1,3,4,2,2]` returns `2`.
2. `nums = [3,1,3,4,2]` returns `3`.
3. `nums = [1,1]` returns `1`.

**Constraints**
- `1 <= n <= 10^5`
- `nums.length == n + 1`
- `1 <= nums[i] <= n`
- Exactly one integer value appears at least twice; all other values appear at most once.
- You must not modify `nums`.
- You must use only constant extra space.

**Follow-up**
How would you solve it if you were allowed `O(n)` extra space (for example, a hash set), or if modifying the array were allowed? Can you also explain why viewing the array as a functional graph `i -> nums[i]` guarantees a cycle whose entrance is exactly the duplicate value?

- Sorting would either modify the array or require copying it first.
- A hash set finds the duplicate quickly, but it uses `O(n)` extra memory.
- The intended trick is to treat each index as a node with one outgoing edge: `i -> nums[i]`. Because values stay in `[1, n]`, following pointers from index `0` must eventually enter a cycle, and the duplicate value is the cycle's entrance.

Start from the constraints, not from code

- Scan the array and remember values seen so far.
- The first value you encounter twice is the answer.
- This is correct and runs in `O(n)` time, but it violates the constant-space requirement, so it is only a warm-up.

Warm up with a disallowed hash-set solution

- Think of index `i` as a node whose next pointer is `nums[i]`. Since every `nums[i]` is between `1` and `n`, once you move from index `0`, you stay inside the node set `1..n`.
- There are `n + 1` indices but only `n` possible next-node values, so following pointers from `0` must eventually revisit a node: a cycle exists.
- The duplicate value is exactly the first node with two incoming edges on that reachable path, so it is the cycle entrance.
- Floyd's algorithm first finds any meeting point inside the cycle, then resets one pointer to the start and advances both one step at a time; they meet at the entrance.

Why Floyd's cycle detection works here

- Start `slow` one step from the start and `fast` two steps from the start.
- Move `slow` by one edge and `fast` by two edges until they meet inside the cycle.
- Then reset a `finder` pointer to index `0`, move `finder` and `slow` one step at a time, and return where they meet. That meeting value is the duplicate number.

Apply Floyd's tortoise-and-hare algorithm

The pointer graph is `0 -> 1 -> 3 -> 2 -> 4 -> 2 -> ...`, so the cycle starts at value `2`.

**Phase 1: find a meeting point inside the cycle**

| step | slow | fast |
|---|---:|---:|
| start | `1` | `3` |
| 1 | `3` | `4` |
| 2 | `2` | `4` |
| 3 | `4` | `4` |

They first meet at value `4`, which is inside the cycle but is not necessarily the duplicate.

**Phase 2: find the cycle entrance**

| step | finder | slow |
|---|---:|---:|
| start | `0` | `4` |
| 1 | `1` | `2` |
| 2 | `3` | `4` |
| 3 | `2` | `2` |

Now both pointers meet at `2`, so the duplicate number is `2`.

Dry run on nums = [1,3,4,2,2]

- Returning the first `slow == fast` meeting point directly. That point is somewhere inside the cycle, not always the duplicate value itself.
- Starting both pointers at `nums[0]`; that can make them appear to meet immediately before any real progress. Use one step vs. two steps at initialization.
- Mixing up indices and values, or subtracting `1` as if the graph were zero-based on `1..n`. The values already are valid next indices for this construction.
- Using sorting or a hash set in the final answer, which breaks the read-only or constant-space constraints.

Common mistakes

- Smallest valid input: `[1,1]` immediately forms a one-node cycle, so the answer is `1`.
- A duplicate may appear three or more times, such as `[2,5,9,6,9,3,8,9,7,1,4]`; the entrance is still `9`.
- The duplicate value can appear in the first array slot, the last slot, or only after a long tail before the cycle begins.
- The answer is the repeated **value**, not the index of one occurrence.

Edge cases to test mentally

Treating the array as a functional graph lets Floyd's cycle detection find the duplicate in `O(n)` time with `O(1)` extra space, without modifying `nums`.