Find the first missing positive integer in an array of integers

Question

The problem is the one explained in Given an unsorted integer array, find the first missing positive integer

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in \$O(n)\$ time and use constant space.

I am trying to learn Java 8+ and wrote the following code. Request any improvisations possible.

int firstPositive(int[] inputArray) {

    //Convert all negative numbers to 0.
    IntStream.range(0, inputArray.length).forEach(idx -> {
        if (inputArray[idx] < 0) inputArray[idx] = 0;
    });

    IntStream.range(0, inputArray.length).forEach(idx -> {
        if (Math.abs(inputArray[idx]) == 0) {
            inputArray[0] = -Math.abs(inputArray[0]);
        }
        else if (Math.abs(inputArray[idx]) - 1 < inputArray.length && inputArray[Math.abs(inputArray[idx]) - 1] > 0) {
            inputArray[Math.abs(inputArray[idx]) - 1] *= -1;
        }
    });

    OptionalInt res = IntStream.range(0, inputArray.length).filter(idx -> inputArray[idx] >= 0).findFirst();

    if (res.isPresent()) {
        return res.getAsInt()+1;
    }

    return inputArray.length+1;
}

Answer 1

Instead of

if (res.isPresent()) {
    return res.getAsInt()+1;
}

return inputArray.length+1;

you could make use of the orElse method of OptionalInt:

return res.orElse(inputArray.length) + 1;

Answer 2

Performance and readability are often a trade off. This \$O( n \log n)\$ solution just misses the \$O(n)\$ target, because we must sort the pre-filtered array, but it’s much easier to reason about a map/reduce in my opinion.

Integer[] nums = {1,2,0};
//Integer[] nums = {3,4,-1,1};
//Integer[] nums = {1,2,4};
//Integer[] nums = {1};
//Integer[] nums = {0};

 Integer result = 
    Arrays.stream(nums)
        .filter(x -> x > 0)
        .sorted()
        .reduce(1, (prev, curr) -> (prev == curr) ? curr + 1 : prev );

System.out.println(result);

I generally find it a bit strange that you’re using streams to generate what is essentially a loop (forEach) instead of turning the array into a stream and leveraging the power streams give you.

Answer 3

There is a much easier solution which is strictly \$\Theta(n)\$. Given \$\ell\$ the input list:

• Filter for just positive numbers: \$\ell_{>0} = \{i \in \ell\mid i > 0\}\$
• Compute the maximum and the sum of the elements of \$\ell_{>0}\$. Namely, \$m = \max \ell_{>0}\$ and \$ s = \sum _ {i \in \ell_{>0}} i\$
• Now there are two cases: whether it is missing a number in \$[1, m)\$ or it is missing \$m+1\$.
• We know that \$1 + 2 + \dots + m=m\times(1+m)/2\$. Call this sum \$t\$. Compare \$t\$ with \$s\$. If they are equal, it means that the sum is complete, so return the next integer, \$m+1\$. Otherwise, the difference will tell you which number is missing: \$t-s\$.

You can achieve constant space by storing just three numbers: \$m\$, \$s\$ and \$t\$. Where \$m\$ and \$s\$ will require \$|\ell|\$ steps to be computed. Consider this pseudocode.

m = 0 # You can safely assume 0 here (or l[0] if you wish)
s = 0
for i in l:
   if i > 0:
     s += i
     if i > m:
       m = i

t = m*(m+1) /2

Of course, then computing \$t\$ is \$\Theta(1)\$.