**First Missing Positive**

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

**Example**

Given `[1,2,0]`

return `3`

, and `[3,4,-1,1]`

return `2`

.

**Challenge**

Your algorithm should run in O(*n*) time and uses constant space.

public int firstMissingPositive(int[] A) { if (A.length == 0) { return 1; } int i = 0; while (i < A.length) { if (A[i] != i + 1) { if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) { swap(A, i, A[i] - 1); } else { A[i] = 0; i++; } } else { i++; } } for (int j = 0; j < A.length; j++) { if (j + 1 != A[j]) { return j + 1; } } return A.length + 1; } public void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; }