[Java] Find all duplicates in array of positive elements in range 1 to N

Given an array where each value is in the range 1..N, find all duplicates.

We can easily do this in O(N) time with additional O(N) space tracking each element in a set, then seeing if we find multiple times the same element.

Sorting in O(N log N) would allow us to use O(1) space to find same result.

If we are allowed to modify the input though, we can do this in O(N) time and O(1) space by modifying the input array while walking on it.

Since all elements are in range 1..N, it means each would point to a valid cell in the array in range 0..N-1.

We walk over the array and look at the cell the current element points to, if we find a negative value, some other element pointed to it before us and we are a duplicate, otherwise we flip the value in that cell and continue.

You can find my implementation of findAllDuplicates on my Gist along with some tests in FindAllDuplicatesJTests.