Find the Duplicate Number (Deprecated)

Find the duplicate number in an array AND use O(1) space. Tags: Search

Try It!

Discussion

Diagram

Video

As an anime video!

Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        hare = nums[0]
        tortoise = nums[0]
        while True:
            hare = nums[nums[hare]]
            tortoise = nums[tortoise]
            if hare == tortoise:
                break
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
        return ptr1