### First Missing Positive Solution - The Coding Shala

Home >> Interview Prep >> First missing positive

In this post, we will learn how to solve the First Missing Positive problem and will implement its solution in Java.

## First Missing Positive Problem

Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:
Input: nums = [1,2,0]
Output: 3

Example 2:
Input: nums = [3,4,-1,1]
Output: 2

## First Missing Positive Java Solution

### Approach 1

Time Complexity: O(n)
Space Complexity: O(1)

The steps are below to solve this problem:

Step 1: The first missing positive number will be in the range of 1 to N+1, where N is the length of the array. So Other than these numbers we can ignore, make this change in the array.

Step 2: Now we will take the array elements as the index(their original position), and at the numbers' original position will make the array element negative so later we can check this number is available in the array.

Step 3: now find the first non-negative number in the array that is our first missing positive number.

Step 4: if we couldn't find the non-negative number then return N+1.

for example:
array => [3,4,-1,1]
after step 1:  array => [3,4,5,1]   N = 4
in step 2:    array[0] = 3 so array is => [3,4,-5,1]
array[1] = 4 so array is => [3,4,-5, -1]
array[2] = 5 skip
array[3] = 1 so array is => [-3, 4, -5, -1]

In step 3, we have the first non-negative number is 4 at index 1 to return index+1 = 2

Java Program:

```class Solution {
public int firstMissingPositive(int[] nums) {
int N = nums.length;
// fist positive number range is 1 to N+1
// ignore other numbers
for (int i = 0; i < N; i++) {
if (nums[i] <= 0 || nums[i] > N) nums[i] = N + 1;
}

// make numbers negative at their original index
for (int i = 0; i < N; i++) {
// take num as index now
// -1 because numbers are started with 1
int index = Math.abs(nums[i]) - 1;

// make negative at index
if (index >= 0 && index < N && nums[index] > 0) {
// number is available in array
nums[index] = -1 * nums[index];
}
}

// now find first non-negative number that is our first missing positive number
for (int i = 0; i < N; i++) {
if (nums[i] > 0) {
return i + 1;
}
}

// if non-negative number is not there
return N + 1;
}
}
```

### Approach 2

Using HashSet.

Time Complexity: O(n)
Space Complexity: O(n)

Java Program:

```class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();

for (int i = 0; i < nums.length; i++) {
}

int i = 1;
int res = -1;
while (true) {
if (!set.contains(i)) {
res = i;
break;
}
i++;
}

return res;
}
}
```

Other Posts You May Like

1. Hi people
I have created a small video trying to explain the O(n) time and O(1) space complexity approach, please check this out :)