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