Given an array of n integers, each between 1 and n-1 inclusive, can you detect duplicates in O(1) space and O(n) time?
Assume that the input is available as an array (with O(1) lookup time). Note that there must be at least one duplicate due to the pigeonhole principle.
The trick is to treat each integer as an index of the input array, such that it points to another integer in the input i.e. treat it as a “pointer”.
There are a few things to note that will help us solve this:
Hence, if we create a sequence by following pointers starting with the last integer, the duplicate integers will be those that point to the beginning of a cycle.
Fortunately, cycle detection is a well-known problem in Computer Science, and there are a few algorithms that can solve this optimally in O(n) time and O(1) space: Floyd or Brent’s algorithms.
The visualisation above shows duplicate detection for a randomised array of 10 integers, using Floyd’s algorithm. The position of the first repeated subsequence is marked in red, and duplicates are marked in orange.
It’s worth noting that cycles can be detected more quickly at the expense of memory.
© Jason Davies 2012.