Find First Missing Positive

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

Problem:

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.


Idea:

Say the array contains n numbers
Use the array index to indicate 1...n, the first missing positive must either be:
1. a number in [1...n]
2. n+1 (i.e. no missing positive in this array)

3 loops:

1. filter invalid numbers (<0 | >n), they won't help us get the answer so just set them to 0
2. for each number at A[i], set A[abs(A[i])] to negative
   abs(A[i]) - the index - is the indicator showing that positive number exists in the array
   Special case: if A[abs(A[i])] == 0, set it to an invalid number to avoid possible mis-counting during further iterations
   Here I set it to a negative number whose abs is > n so it won't be counted in further iterations
3. The first index i that A[i] >= 0 is the missing number (not affected by the previous iterations)

public class Solution {
    public int firstMissingPositive(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        for (int i=0; i<A.length; i++) {
            if (A[i] < 0) A[i] = 0;
            else if (A[i] > A.length) A[i] = 0;
        }
        for (int i=0; i<A.length; i++) {
            int loc = Math.abs(A[i]) - 1;
            if (loc >= 0 && loc < A.length) {
                if (A[loc] > 0) {
                    A[loc] = - A[loc];
                }
                else if (A[loc] == 0) {
                    A[loc] = - A.length - 1;
                }
            }
        }
        for (int i=0; i<A.length; i++) {
            if (A[i] >= 0) return i + 1;
        }
        return A.length + 1;
    }
}