Floyd’s Cycle Finding Algorithm

If we constraint the input of Finding Duplicates to:

NOTE

input array $a[1,...,n]$ with $a[i]\in \{1,\dots ,n-1\}$

then we can use a better algorithm with $O(n)$ time and $O(1)$ memory

Overview

The idea is to start with the two pointers slow and fast, both starting at the head of the linked list.

• While traversing the List:
  • slow pointer will move one step at a time.
  • fast pointer moves two steps at a time.
  • If there’s a cycle, the fast pointer will eventually catch up with the slow pointer within the cycle because it’s moving faster.
  • If there’s no cycle, the fast pointer will reach the end of the list (i.e., it will become NULL).
• When the slow and fast pointers meet, a cycle or loop exists

Application

Given: Array $a[1,...,n]$ with $a[i]\in \{1,\dots ,n-1\}$ Goal: Find two indices $i\ne j$ with $a[i]=a[j]$ Constraints: time $O(n)$, memory $O(1)$ We observe the graph $D=(V,A)$ with $V=[1,\dots ,n]$ $A=\{(i,a[i])|1\le i\le n\}$

floyd's cycle finding example.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

n

Link to original

We observe the subgraph $D_n$ (nodes and edges that are reachable from $n$)

floyd's cycle finding example Dn.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

n

Link to original

We define $x_0=n$ $x_t=a[t_{t-1}]$ Claim: There is $t\le n$ such that $x_t=x_{2t}$ Proof: Let $r=\lceil \frac{k}{l}\rceil \cdot l-k\ge 0$ so $k+r=\lceil \frac{k}{l}\rceil l⟹x_{k+r}=x_{2(k+r)}$ and $t:=k+r=\lceil \frac{k}{l}\rceil l<\left(\frac{k}{l}+1\right)l=k+l\le n$

Now we can use the two pointers to solve the task.

Find $t$

slow=a[n]
fast=a[a[n]]
t=1
while(slow!=fast)
	slow=a[slow]
	fast=a[a[fast]]
	t=t+1

Claim: Let $t\le n$ with $x_t=x_{2t}$ then $x_{t+k}=x_k$ Proof: $x_t=x_{2t}⟹2t=t+p\cdot l$ for some $p\in \mathbb{N}$ $⟹t=p\cdot l$ for some $p\in \mathbb{N}$ $⟹x_{k+t}=x_k$

find $i,j$ with $a[i]=a[j]$

fast=n
while(slow!=fast)
	i=slow
	j=fast
	slow=a[slow]
	fast=a[fast]
return i,j