4
\$\begingroup\$

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;
}
\$\endgroup\$
1

3 Answers 3

4
\$\begingroup\$

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;
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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)\$.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Clever solution, but it only works when exactly 0 or 1 positive integer is missing from the array. For example, it would fail with [1,2,4,5,7]. Also you stated that the computing time is O(1), but it is O(n) where n is the input array length. \$\endgroup\$
    – potato
    Aug 18, 2019 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.