287. Find the Duplicate Number
Given an array nums containing 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.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2] Output: 3
Note:
- 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.
---
Intuition
Numbers are in the array from 1 through N,
If we consider array element to be index to travel to, and remember that N + 1 elements exists.
This means all values point to position that definitely exists, then array will be traversed infinitely and there is a cycle.
Array elements are from 1.. N .. No element is 0
This means 0th element is not part of the cycle
This reduces to linked list cycle detection problem
Two pointers fast, slow ..
slow = array[slow]
fast = array[array[fast]]
Till they meet
Once they meet, as in values are same, that could mean either we found real duplicates, or they ended up at same array index
Start another pointer now at array[0]
Move both array[0] and slow by one step, they will intersect at the duplicate
--
Time - O(n)
Space - O(1)