[LeetCode] First Missing Positive (Java)

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 uses constant space.

Analysis

We are required to use constant space. So we need to use the array. We can put the element, which value is i, in position i – 1. After we finishing doing this, we can go through the array to find the first missing positive integer.

For example, the original array is 3 4 -1 1. We will make it like 1 4 3 -1. And we can know the missing number is 2 easily.

Code

Complexity

We only needs $O(n)$ time to swap the elements in array. So the complexity is $O(n)$.

  • random

    return A.length + 1;
    probably needs to be
    return Collections.max(A) + 1; // replace Collections.max() with what works with an int[]

    Otherwise it will fail for cases where the list is similar to [1, 2, 1, 1, 1].

  • random

    Nvm, seems like it will work after all. Couldn’t remove the earlier comment!