Find all duplicates in an array

Every value is between 1 and n and appears once or twice. Use each value as an index and flip that slot negative; a slot that is already negative means the value is a repeat.

The idea

Values run from 1 to n, so every value v owns a slot in the array itself: index v - 1. The sign of that slot is a free bit of memory. The first time v turns up, flip its slot negative. If v turns up again, its slot is already negative, so v is a duplicate. The values themselves are never lost, only their signs change, which is why each read takes the absolute value.

Code

public IList<int> FindDuplicates(int[] nums) {
    var result = new List<int>();
    foreach (int x in nums) {
        int i = Math.Abs(x) - 1; // x may already be flipped: its slot is |x| - 1
        if (nums[i] < 0) result.Add(i + 1); // slot already flipped: value seen before
        else nums[i] = -nums[i]; // first sighting: flip the slot to mark it
    }
    return result;
}

Tips

• Read the value with Math.Abs: an element may already have been flipped by an earlier value pointing at its slot.
• This works only because every value is a valid index (1 to n). First missing positive uses the same "value as index" idea, with swaps instead of signs.
• If the caller needs the input untouched, flip every slot back to positive before returning: still O(n) time and O(1) extra space.

In the .NET library

foreach over an int[] reads nums[k] fresh on each step (the compiler turns it into an index loop), so writing to the array inside the loop is allowed. For a List<T> it would throw InvalidOperationException.