LeetCode 287: Find the Duplicate Number (Floyd's Tortoise and Hare)

Today we solve LeetCode 287 - Find the Duplicate Number, a classic trick question where an array can be viewed as a linked list with a cycle.

Source: https://leetcode.com/problems/find-the-duplicate-number/

English

Problem Summary

You are given an integer array nums containing n + 1 integers where each integer is in the range [1, n]. There is only one repeated number, but it may appear more than once. Return that duplicate number without modifying the array and using only constant extra space.

Key Insight

Interpret index transitions as a linked list: from index i, next node is nums[i]. Because values are in [1, n] and there are n + 1 nodes reachable from index 0, a cycle must exist. The duplicate value is the cycle entrance.

Baseline Approaches

- Hash set: easy and linear time, but O(n) extra space (violates constraint).
- Sorting: can find duplicate neighbors, but modifies array or needs copy.
- Binary search on value range + counting: O(n log n) time, O(1) extra space.

Optimal Algorithm (Floyd Cycle Detection)

Phase 1 (find meeting point):
1) slow = nums[0], fast = nums[0].
2) Move slow = nums[slow], fast = nums[nums[fast]] until they meet.

Phase 2 (find cycle entrance):
1) Reset slow = nums[0].
2) Move both one step each: slow = nums[slow], fast = nums[fast].
3) First meeting index/value is the duplicate number.

Why Phase 2 Works

Let distance from start to cycle entrance be a, distance from entrance to first meeting point be b, and cycle length be c. At meeting:

2(a + b) = a + b + k*c ⇒ a + b = k*c ⇒ a = k*c - b.

So one pointer from start and one from meeting point, both moving 1 step, will meet exactly at the entrance (duplicate).

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Starting from wrong node/index and causing off-by-one confusion.
- Using visited array/set, which breaks the constant-space requirement.
- Returning meeting point from phase 1 directly without phase 2.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[0]

    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    slow = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[0]

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
  let slow = nums[0];
  let fast = nums[0];

  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
};

中文

题目概述

给定一个长度为 n + 1 的数组 nums，其中每个数字都在 [1, n] 范围内。已知只有一个数字重复出现（重复次数可能大于 2），要求在不修改数组且额外空间为常数的条件下返回这个重复数字。

核心思路

把数组看成“链表跳转关系”：从位置 i 跳到 nums[i]。由于值域限制在 [1, n]，并且节点数是 n + 1，按抽屉原理一定会形成环；环的入口对应的值就是重复数字。

常见基线解法

- 哈希集合判重：时间 O(n)，但空间 O(n)，不满足常数空间。
- 排序后找相邻重复：会修改原数组，或需要额外拷贝。
- 按值域二分 + 计数：时间 O(n log n)，空间 O(1)。

最优算法（Floyd 快慢指针判环）

第一阶段（找相遇点）：
1）slow = nums[0]，fast = nums[0]。
2）循环前进：slow = nums[slow]，fast = nums[nums[fast]]，直到两者相遇。

第二阶段（找环入口）：
1）将 slow 重置到 nums[0]。
2）两者都每次走一步：slow = nums[slow]，fast = nums[fast]。
3）再次相遇的位置（值）就是重复数字。

为何第二阶段一定正确

设起点到环入口距离为 a，入口到第一次相遇点距离为 b，环长为 c。第一次相遇时满足：

2(a + b) = a + b + k*c，可得 a = k*c - b。

这意味着一个指针从起点出发、另一个从相遇点出发，每次都走一步，它们会在环入口相遇，即重复数字。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 起点或索引定义混乱，导致实现偏移一位。
- 偷用 visited/set 导致空间超限。
- 第一阶段相遇后直接返回，忘记第二阶段找入口。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[0]

    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    slow = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[0]

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
  let slow = nums[0];
  let fast = nums[0];

  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
};