O(n) time and O(1) space, on an array of arbitrary integers — which rules out sorting and
rules out a hash set, so the array has to become its own hash table. The key observation is that the
answer is always in 1..n+1, so only values in 1..n can possibly matter and
value v gets exactly one home: index v−1. Three
things go wrong when people write this from memory, and this page lights all three up: values
≤ 0 or > n must be left alone rather than indexed with; the inner loop must
be a while, because one swap drops a new stray value into the slot you just vacated; and
the exit test must be nums[nums[i]-1] != nums[i] — comparing values, not
i != nums[i]-1 comparing indices, or a duplicate swaps back and forth until the
clock runs out. Then one linear read: the first index not holding index+1 gives the
answer, and if every index is satisfied the answer is n+1.
while is not quadratic:
every swap parks one value at its permanent home, so there are at most n swaps in the whole
run. The answer lives in 1..n+1, which is why anything outside that window can be
ignored outright.