273. An array of n integers holds values in [0, n − 1]. Detect duplicates using O(1) extra space.
MediumSearching & selection
Technical
Show model answer
General approaches are pairwise comparison (O(n²)), sorting then scanning (O(n log n)) and a hash set (O(n) time, O(n) space). The value range allows a marking trick: for each element, look at index `|a[i]|`; if the value there is already negative, `|a[i]|` has been seen before; otherwise negate it.
This is O(n) time and O(1) extra space but modifies the input (restore by taking absolute values afterwards). Zero is a problem because −0 equals 0, so shift values by one or use the related trick of adding n to `a[a[i] % n]` and checking which slots exceed 2n − 1.