Given an array
n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Input: [1,3,4,2,2] Output: 2
Input: [3,1,3,4,2] Output: 3
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
Solution: Floyd’s Tortoise and Hare (Cycle Detection)
If we interpret
nums such that for each pair of index \(i\) and value \(v_i\), the “next” value \(v_j\) is at index \(v_i\), we can reduce this problem to cycle detection. See the solution to Linked List Cycle II for more details.
Because each number in
nums is between \(1\) and \(n\), it will necessarily point to an index that exists. Therefore, the list can be traversed infinitely, which implies that there is a cycle. Additionally, because \(0\) cannot appear as a value in
nums cannot be part of the cycle. Therefore, traversing the array in this manner from
nums is equivalent to traversing a cyclic linked list.
class Solution(object): def findDuplicate(self, nums): """ :type nums: List[int] :rtype: int """ tortoise = nums hare = nums while True: tortoise = nums[tortoise] hare = nums[nums[hare]] if tortoise == hare: break # Find the "entrance" to the cycle. ptr1 = nums ptr2 = tortoise while ptr1 != ptr2: ptr1 = nums[ptr1] ptr2 = nums[ptr2] return ptr1