Find All Duplicates in an Array

Problem

You are given an integer array nums of length n where every value lies in the range [1, n]. Each value appears either once or twice. Return a list of every value that appears twice, in any order. Aim for O(n) time and O(1) extra space, not counting the output list.

• The array is non-empty and has at most 200,000 elements.
• Every value is between 1 and n inclusive, where n is the array length (the in-place trick depends on this).
• Each value occurs at most twice.

Examples

• nums = [6, 1, 5, 3, 5, 2, 6, 4] → [5, 6]. Both 5 and 6 appear twice.
• nums = [2, 3, 2] → [2].
• nums = [1] → []. Nothing repeats.

Hints

1. A hash set finds duplicates in O(n) time and O(n) space; the constraint 1 <= nums[i] <= n hints that you can avoid the set.
2. Every value v has a natural "slot" in the array: index v - 1. Can that slot remember whether v has been seen?
3. Flip the sign at index |v| - 1 when you see v; if it is already negative, v is a duplicate.