287. Find the Duplicate Number

Problem Link

To solve this problem without modifying the array and using constant extra space, we treat the array as a linked list where each index points to the value at that index.

Since the values range from 1 to n, there must be a duplicate, which creates a cycle in this implicit linked list. To detect this cycle, we use Floyd’s Tortoise and Hare algorithm.

In the first phase, we initialize two pointers, slow and fast, both starting at index 0. On each step, slow moves one step forward, while fast moves two steps forward. If a cycle exists, the two pointers will eventually meet inside the cycle.

Once the pointers meet, we start the second phase to find the entry point of the cycle, which corresponds to the duplicate number. We reset one pointer to the start and move both pointers one step at a time. The point where they meet again is the duplicate value.

Finally, we return this value as the answer. This approach runs efficiently while satisfying the problem’s constraints.

Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\)

PythonGo

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        slow, fast = 0, 0
        while fast < len(nums):
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        first, second = 0, slow
        while first != second:
            first = nums[first]
            second = nums[second]
        return first

func findDuplicate(nums []int) int {
    var slow, fast int
    for fast < len(nums) {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    first, second := 0, slow
    for first != second {
        first = nums[first]
        second = nums[second]
    }
    return first
}

---