First Duplicate in O(n) Time, O(1) Space

Problem Given an array of n integers where every value is in the range [1, n], find the first value that appears a second time (the duplicate whose second occurrence comes earliest), using O(1) extra space.

Input / Output

• Input: an array nums with values in [1, n].
• Output: the first value that repeats, or a sentinel (e.g. -1) if none does.

Constraints

• Values in range [1, n]; O(n) time and O(1) extra space expected.
• Mutating the array is allowed (if not, that changes the approach).

Example

• [2,3,3,1,5,2] → 3 (its second occurrence precedes the second 2).