Pattern visualizer
Find the Duplicate Number
n+1 numbers squeezed into the range [1,n] guarantees at least one repeat by pigeonhole — but the clever part is turning the ARRAY into a linked list: treat each index i as a node whose 'next' pointer is nums[i]. A repeated value means two different indices point to the same next-index, which is exactly what creates a cycle — and a cycle's entry point is found with the same slow/fast pointer trick used for linked lists. Animated on: nums = [1,3,4,2,2] — find the one repeated number without modifying the array or using extra space..
Floyd's cycle detection, reused from linked lists
nums=[1,3,4,2,2]. Treat each value as a "next pointer": index i points to index nums[i]. A duplicate value means two indices point to the same place — a cycle. Find it with Floyd's slow/fast pointers.
1FUNCTION findDuplicate(nums):2 set slow to nums[0], fast to nums[nums[0]]3 WHILE slow is not equal to fast:4 move slow to nums[slow] (one hop), fast to nums[nums[fast]] (two hops)5 set p1 to 0, p2 to fast6 WHILE p1 is not equal to p2:7 move p1 to nums[p1] and p2 to nums[p2] (one hop each)8 RETURN p1
← / → step · space play · Home restart