1 article
The O(n) time, O(1) space trick for arrays that hold numbers in a known range 1..n: place each value at its natural index, then scan once for anything out of place. Missing numbers, duplicates, and corrupt pairs fall out as a natural consequence.