[Java] Find first missing positive integer in array with duplicates, zeros and negative values

Here is a problem: given an array of integer which can contain duplicates, zeros and negatives, find the first missing positive integer.

If the array does not contain a positive integer at all, the answer is 1, if it contains all integers between 1..N, where N is the length of the array, the answer is N+1.

The requirement is to do this in linear time AND constant space. The input array can be modified.

I think the difficulty of this problem comes from the fact that we allow duplicates and do not want to use additional space.

(1) My first thought was to follow a logic similar to finding a repeated element using Brent's algorithm, Floyd's algorithm and binary search. But we can't apply those since we can have negative values, missing items and multiple duplicates.

If we wouldn't allow duplicates, this would be a very simple sum of all items excluding zeros and negatives, then comparing the sum with the expected sum of all numbers 1..N where N is the amount of positives we encountered which is quickly done with the formula: 

N(N+1)/2

Our result would then be the difference of the two.

Using extra space we can also solve this easily by creating a set of seen numbers, then doing a loop 1..N and testing whether the given element was seen. Our answer is the first unseen number.

Another solution would be if we could sort the array in linear time, which in some cases, for example radix sort or counting sort, can be achieved, albeit with some limitations: the range of allowed numbers must be known AND small enough, additionally, we require extra space.

If we can reach a solution in O(N) time and O(1) space and we are told we can modify the array, it means there must be some way of processing our input so that we can reach the solution in multiple passes.

I have found this Stackoverflow answer, which gives an algorithm but doesn't explain why it works. Luckily it was written well enough that understanding it with some examples is easy.

Assume we have a perfect array of all positives 1..N, no duplicates and no missing values:

1, 2, 3

Remember our first though (1) used a similar idea: each array value can be converted to 0-based (value - 1) 0..N-1 and would therefore point to a unique cell in the array. 

For each positive value in the array, we pick the cell it would point to and mark it somehow to indicate we found its pointer. For example we can turn the value in the cell negative.
At the end we would have an array of only negative values:

-1, -2, -3
 

Now, if there are duplicates, we would have multiple references to the same cell, therefore we need to be careful keeping negative values, one we set a marker, it cannot be undone. The goal is knowing if at least one value in the array was pointing to a particular cell.

Additionally, since we are using array values as indices in the array, we need to consider the absolute value in case it was negative (one of our markers).

The available cells in an array are 0..N-1 which means we can fit all consecutive positive numbers 1..N.

If there is a duplicate, it means some other number can't fit in this range as its place would be taken by the duplicate, therefore we have a missing value.
When a number is missing, the cell it would point to won't be turned negative by our previous logic, for example:

1, 1, 2

There is no value 3 which points to cell 2. Our processing would yield:

-1, -1, 2

When we scan the array again then, if we encounter a positive value, we know that the number pointing to this cell 0-based (therefore the number is equal to cell index + 1) was missing.

If there are no duplicates but simply missing numbers, we would have the same situation:

1, 3, 5

would result in:

-1, 3, -5

If there are more duplicates or missing numbers or a combination of the two, when walking the array we would find the very first missing item every time, even though our array might have multiple positive values left after our processing, example:

1, 1, 6, 7, 4

results in:

-1, 1, 5, -7, 4

Where we have multiple missing numbers, but the first missing is 2.

If the array contained all positive values from 1 to N, then the first missing would be AFTER the end of the array, N+1.

You can check my implementation of findFirstMissingPositiveIntegerWithZerosAndDuplicates on my Gist along with some tests in FindFirstMissingPositiveIntegerWithZerosAndDuplicatesJTests I also make use of a helper function to partition the array.