# File: FindDuplicate.py
# Author: Keith Schwarz (htiek@cs.stanford.edu)
#
# An algorithm for solving the following (classic) hard interview problem:
#
# "You are given an array of integers of length n, where each element ranges
# from 0 to n - 2, inclusive. Prove that at least one duplicate element must
# exist, and give an O(n)-time, O(1)-space algorithm for finding some
# duplicated element. You must not modify the array elements during this
# process."
#
# This problem (reportedly) took CS legend Don Knuth twenty-four hours to solve
# and I have only met one person (Keith Amling) who could solve it in less time
# than this.
#
# The first part of this problem - proving that at least one duplicate element
# must exist - is a straightforward application of the pigeonhole principle.
# If the values range from 0 to n - 2, inclusive, then there are only n - 1
# different values. If we have an array of n elements, one must necessarily be
# duplicated.
#
# The second part of this problem - finding the duplicated element subject to
# the given constraints - is much harder. To solve this, we're going to need a
# series of nonobvious insights that transform the problem into an instance of
# something entirely different.
#
# The main trick we need to use to solve this problem is to notice that because
# we have an array of n elements ranging from 0 to n - 2, we can think of the
# array as defining a function f from the set {0, 1, ..., n - 1} onto itself.
# This function is defined by f(i) = A[i]. Given this setup, a duplicated
# value corresponds to a pair of indices i != j such that f(i) = f(j). Our
# challenge, therefore, is to find this pair (i, j). Once we have it, we can
# easily find the duplicated value by just picking f(i) = A[i].
#
# But how are we to find this repeated value? It turns out that this is a
# well-studied problem in computer science called cycle detection. The general
# form of the problem is as follows. We are given a function f. Define the
# sequence x_i as
#
# x_0 = k (for some k)
# x_1 = f(x_0)
# x_2 = f(f(x_0))
# ...
# x_{n+1} = f(x_n)
#
# Assuming that f maps from a domain into itself, this function will have one
# of three forms. First, if the domain is infinite, then the sequence could be
# infinitely long and nonrepeating. For example, the function f(n) = n + 1 on
# the integers has this property - no number is ever duplicated. Second, the
# sequence could be a closed loop, which means that there is some i so that
# x_0 = x_i. In this case, the sequence cycles through some fixed set of
# values indefinitely. Finally, the sequence could be "rho-shaped." In this
# case, the sequence looks something like this:
#
# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
# ^ |
# | |
# +-----------------------+
#
# That is, the sequence begins with a chain of elements that enters a cycle,
# then cycles around indefinitely. We'll denote the first element of the cycle
# that is reached in the sequence the "entry" of the cycle.
#
# For our particular problem of finding a duplicated element in the array,
# consider the sequence formed by starting at position n - 1 and then
# repeatedly applying f. That is, we start at the last position in the array,
# then go to the indicated index, repeating this process. My claim is that
# this sequence is rho-shaped. To see this, note that it must contains a cycle
# because the array is finite and after visiting n elements, we necessarily
# must visit some element twice. This is true no matter where we start off in
# the array. Moreover, note that since the array elements range from 0 to
# n - 2 inclusive, there is no array index that contains n - 1 as a value.
# Consequently, when we leave index n - 1 after applying the function f one
# time, we can never get back there. This means that n - 1 can't be part of a
# cycle, but if we follow indices starting there we must eventually hit some
# other node twice. The concatenation of the chain starting at n - 1 with the
# cycle it hits must be rho-shaped.
#
# Moreover, think about the node we encounter that starts at the entry of the
# cycle. Since this node is at the entry of the cycle, there must be two
# inputs to the function f that both result in that index being generated. For
# this to be possible, it must be that there are indices i != j with
# f(i) = f(j), meaning that A[i] = A[j]. Thus the index of the entry of the
# cycle must be one of the values that is duplicated in the array.
#
# There is a famous algorithm due to Robert Floyd that, given a rho-shaped
# sequence, finds the entry point of the cycle in linear time and using only
# constant space. This algorithm is often referred to as the "tortoise and
# hare" algorithm, for reasons that will become clearer shortly.
#
# The idea behind the algorithm is to define two quantities. First, let c be
# the length of the chain that enters the cycle, and let l be the length of the
# cycle. Next, let l' be the smallest multiple of l that's larger than c.
# I claim that for any rho-shaped sequence l' defined above, that
#
# x_{l'} = x_{2l'}
#
# The proof is actually straightforward and very illustrative - it's one of my
# favorite proofs in computer science. The idea is that since l' is at least
# c, it must be contained in the cycle. Moreover, since l' is a multiple of
# the length of the loop, we can write it as ml for some constant m. If we
# start at position x_{l'}, which is inside the loop, then take l' more steps
# forward to get to x_{2l'}, then we will just walk around the loop m times,
# ending up right back where we started.
#
# One key trick of Floyd's algorithm is that even if we don't explicitly know l
# or c, we can still find the value l' in O(l') time. The idea is as follows.
# We begin by keeping track of two values "slow" and "fast," both starting at
# x_0. We then iteratively compute
#
# slow = f(slow)
# fast = f(f(fast))
#
# We repeat this process until we find that slow and fast are equal to one
# another. When this happens, we know that slow = x_j for some j, and
# fast = x_{2j} for that same j. Since x_j = x_{2j}, we know that j must be at
# least c, since it has to be contained in the cycle. Moreover, we know that j
# must be a multiple of l, since the fact that x_j = x_{2j} means that taking j
# steps while in the cycle ends up producing the same result. Finally, j must
# be the smallest multiple of l greater than c, since if there were a smaller
# multiple of l greater than c then we would have reached that multiple before
# we reached j. Consequently, we must have that j = l', meaning that we can
# find l' without knowing anything about the length or shape of the cycle!
#
# To complete the construction, we need to show how to use our information
# about l' to find the entry to the cycle (which is at position x_c). To do
# this, we start off one final variable, which we call "finder," at x_0. We
# then iteratively repeat the following:
#
# finder = f(finder)
# slow = f(slow)
#
# until finder = slow. We claim that (1) the two will eventually hit each
# other, and (2) they will hit each other at the entry to the cycle. To see
# this, we remark that since slow is at position x_{l'}, if we take c steps
# forward, then we have that slow will be at position x_{l' + c}. Since l' is
# a multiple of the loop length, this is equivalent to taking c steps forward,
# then walking around the loop some number of times back to where you started.
# In other words, x_{l' + c} = x_c. Moreover, consider the position of the
# finder variable after c steps. It starts at x_0, so after c steps it will be
# at position x_c. This proves both (1) and (2), since we've shown that the
# two must eventually hit each other, and when they do they hit at position x_c
# at the entry to the cycle.
#
# The beauty of this algorithm is that it uses only O(1) external memory to
# keep track of two different pointers - the slow pointer, and then the fast
# pointer (for the first half) and the finder pointer (for the second half).
# But on top of that, it runs in O(n) time. To see this, note that the time
# required for the slow pointer to hit the fast pointer is O(l'). Since l' is
# the smallest multiple of l greater than c, we have two cases to consider.
# First, if l > c, then this is l. Otherwise, if l < c, then we have that
# there must be some multiple of l between c and 2c. To see this, note that
# in the range c and 2c there are c different values, and since l < c at least
# one of them must be equal to 0 mod l. Finally, the time required to find the
# start of the cycle from this point is O(c). This gives a total runtime of at
# most O(c + max{l, 2c}). All of these values are at most n, so this algorithm
# runs in time O(n).
def findArrayDuplicate(array):
assert len(array) > 0
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow = len(array) - 1
fast = len(array) - 1
# Keep advancing 'slow' by one step and 'fast' by two steps until they
# meet inside the loop.
while True:
slow = array[slow]
fast = array[array[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = len(array) - 1
while True:
slow = array[slow]
finder = array[finder]
# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow