> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/first-missing-integer.md).

# First Missing Integer

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

**Example:**

Given `[1,2,0]` return 3,

`[3,4,-1,1]` return 2,

`[-8, -7, -6]` returns 1

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

```java
public class Solution {
    public int firstMissingPositive(int[] A) {
        int i = 0;
        while (i < A.length) {
            if (A[i] >= 1 && A[i] <= A.length && A[A[i] - 1] != A[i]) {
                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            } else
                i++;
        }
        i = 0;
        while (i < A.length && A[i] == i + 1)
            i++;
        return i + 1;
    }
}
```