Q44: Find the Duplicate Number. - DSA Patterns (Multi-Lang)

In Simple Words: Floyd's Tortoise and Hare Cycle Detection on implicit graph i -> nums[i].

Intersection: slow = nums[slow], fast = nums[nums[fast]] until they meet.
Find entrance: Reset slow2 = 0, move slow and slow2 at 1 step/iteration until they collide.

Time: $O(N)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def findDuplicate(nums: list[int]) -> int:
    slow, fast = 0, 0
    # Phase 1: Detect cycle
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    # Phase 2: Find cycle entrance
    slow2 = 0
    while True:
        slow = nums[slow]
        slow2 = nums[slow2]
        if slow == slow2:
            return slow