Cyclic Sort

Medium

When values are 1..n, each value has a home index. Swap until everything is home, then whatever is misplaced is your answer.

in placelinearindex mapping

TimeO(n)

SpaceO(1)

InputA permutation of 1..n, possibly with a duplicate

Value v belongs at index v-1. Keep sending values home.

swaps0

1 / 13

i = 0

while i < n:

j = a[i] - 1

if a[i] != a[j]: swap(a[i], a[j])

else: i++

scan for the first index where a[i] != i+1

Why it matters

Every swap places at least one value correctly, so the loop runs at most 2n times.

Practise this

Keyboard

space play← → stepr restartctrl K search