# [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.

## Complexity

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