# First Missing Positive

This page explains Java solution to problem `First Missing Positive` using `Array` data structure.

## Problem Statement

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

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class FirstMissingPositive {
public int firstMissingPositive(int[] arr) {

int positiveNumberIndex = -1;
//Since we have to return smallest missing positive number,
//let's move all the negative number to the end
for(int i = 0; i < arr.length; i++) {
if(arr[i] > 0) swap(arr, i, ++positiveNumberIndex);
}

//Now problem reduces to finding a missing positive number within a set of +ve numbers
for(int i = 0; i <= positiveNumberIndex; i++) {
int index = Math.abs(arr[i]) - 1;
if(index <= positiveNumberIndex && arr[index] > 0) arr[index] = -1 * arr[index];
}

//Now number which is still positive, that number's index is missing number
for(int i = 0; i <= positiveNumberIndex; i++) {
if(arr[i] > 0) return i + 1;
}

return Math.min(positiveNumberIndex + 1, arr.length) + 1;
}

private void swap(int[] arr, int from, int to) {
int element = arr[from];
arr[from] = arr[to];
arr[to] = element;
}
}

``````

## Time Complexity

O(N)
Where N is total number of elements in an input array.

O(1)