Problem Description

You are 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 duplicate number.

You must solve the problem without modifying the array and using only constant extra space.

Example:

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

Constraints:

• 1 <= n <= 10⁵
• nums.length == n + 1
• 1 <= nums[i] <= n
• All integers appear only once except for one integer which appears twice or more.

---

Intuition

Since the array has n + 1 numbers and all numbers are from 1 to n, the Pigeonhole Principle ensures that at least one number must repeat.

We can’t sort or modify the array, so we need a method that:

• Uses O(1) extra space.
• Has O(n) time complexity.

The most elegant way to achieve this is by using Floyd’s Tortoise and Hare (Cycle Detection) algorithm — the same concept used in linked list cycle detection.

---

Approach: Floyd’s Tortoise and Hare (Cycle Detection)

We treat the array like a linked list:

• The value at each index represents a pointer to the next index.
• Because one value repeats, a cycle will form.

For example:

nums = [1,3,4,2,2]
Indexes: 0 1 2 3 4
Values:  1 3 4 2 2

This means:

0 → 1 → 3 → 2 → 4 → 2 → 4 → ...

Here, 2 and 4 form a cycle.

We’ll use two pointers:

1. slow moves one step at a time.
2. fast moves two steps at a time.

When they meet, a cycle exists.
Then we find the start of the cycle, which corresponds to the duplicate number.

---

Step-by-Step Algorithm

1. Phase 1 – Detect the cycle
   • Move slow by one step: slow = nums[slow].
   • Move fast by two steps: fast = nums[nums[fast]].
   • Continue until they meet.
2. Phase 2 – Find the entry point of the cycle
   • Reset slow to nums[0].
   • Move both slow and fast one step at a time.
   • The position where they meet again is the duplicate number.

---

Java Code Implementation

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: Detect intersection point in the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: Find the entry point of the cycle (duplicate)
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

---

Dry Run Example

Input:

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

Execution:

Step	slow	fast	Description
Init	3	3	Both start at nums[0]
1	nums[3]=4	nums[nums[3]]=2	slow=4, fast=2
2	nums[4]=2	nums[nums[2]]=3	slow=2, fast=3
3	nums[2]=3	nums[nums[3]]=2	slow=3, fast=2
4	nums[3]=4	nums[nums[2]]=3	slow=4, fast=3
5	nums[4]=2	nums[nums[3]]=4	slow=2, fast=4
6	nums[2]=3	nums[nums[4]]=2	slow=3, fast=2
…	Eventually slow == fast

After detection, reset slow to nums[0] = 3 and move both one step at a time until they meet → duplicate = 3.

---

Time and Space Complexity

Complexity	Analysis
Time Complexity	O(n) — Each pointer moves at most n steps
Space Complexity	O(1) — Only constant space is used

---

Alternate Approaches

1. Using HashSet – Easy but uses O(n) extra space.
2. Sorting – Detect duplicates by comparing adjacent elements, but modifies array and takes O(n log n) time.
3. Binary Search on Value Range – Uses O(1) space and O(n log n) time; based on counting numbers ≤ mid.

---

Summary

• The key insight is that the array can be visualized as a linked list.
• Floyd’s cycle detection finds the duplicate efficiently.
• This is an elegant, optimal solution with O(n) time and O(1) space.