Here values in nums is a permutation of the indices. If we consider i and nums[i] as consecutive nodes of a linked list, we have a permutation of the indices in the linked list.
Say nums[i] = 2 and nums[j] = 2. This creates a cycle.
With fast and slow pointers we can find the cycle head and thus the duplicate number.
Time: 
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
next = lambda i: nums[i]
slow, fast = 0, 0
while True:
slow = next(slow)
fast = next(next(fast))
if slow == fast:
break
fast = 0
while slow != fast:
slow = next(slow)
fast = next(fast)
return fast
unreasonably effective 
Leave a comment