top of page
Search

# First Missing Positive

Updated: Mar 24, 2021

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 0 <= nums.length <= 300

• -231 <= nums[i] <= 231 - 1

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?

Solution:

```class Solution {
public int firstMissingPositive(int[] nums) {
if(nums.length==0) return 1;
int lastPositiveindex=partition(nums)+1;

for(int i=0;i<lastPositiveindex;i++){
int k=Math.abs(nums[i]);
if(k<=lastPositiveindex)
nums[k-1]=(nums[k-1]<0)?nums[k-1]:-nums[k-1];
}
for(int i=0;i<lastPositiveindex;i++){
if(nums[i]>0){
return i+1;
}
}
return lastPositiveindex+1;
}

public int partition(int[] nums)
{
int j=-1;
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
j++;
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
return j;
}
}
```

## Recent Posts

See All

Smallest String With A Given Numeric Value

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

bottom of page