**source:**https://leetcode.com/problems/first-missing-positive/**C/C++**

**Solution to LeetCode**problem

**41**.

**First Missing Positive**.

## Problem

Given an unsorted integer array `nums`

, return the smallest missing positive integer.

You must implement an algorithm that runs in `O(n)`

time and uses constant extra space.

## Examples

**Example 1:**

Input:nums = [1,2,0]

Output:3

Explanation:The numbers in the range [1,2] are all in the array.

**Example 2:**

Input:nums = [3,4,-1,1]

Output:2

Explanation:1 is in the array but 2 is missing.

**Example 3:**

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

Output:1

Explanation:The smallest positive integer 1 is missing.

## Constraints

`1 <= nums.length <= 10`

^{5}`-2`

^{31}<= nums[i] <= 2^{31}- 1

## Solution

- Because we are looking for a positive integer, we can “remove” all the negative numbers (We set them to
`0`

). - If we have an array of size
`n`

with numbers`from 2 to n+1`

we know that the value missing is`1`

; if the array has all the values`[1,n]`

, then the first missing integer is`n+1`

. So, we are looking for an integer in the range`[1, n+1]`

. - For each number, we verify if its absolute is a number in the range
`[1,n]`

. - If so, we can verify the value present at the index that should be for that number if the array was sorted (with values from
`1 to n`

).- If the value at that position is
`> 0`

, we mark them as negative. - If the value is
`0`

we set it to`-(n+1)`

.

- If the value at that position is
- Once completed, we iterate through the array, and the first element with value
`>0`

that’s the missing integer (`index+1`

).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n=nums.size();
for (int i=0;i<n;++i)
if (nums[i]<0) nums[i] = 0;
for (int i=0;i<n;++i){
int absv = abs(nums[i]);
if (absv >= 1 && absv <= n) {
if (nums[absv-1] > 0)
nums[absv-1] *= -1;
else if (nums[absv-1] == 0)
nums[absv-1] = -1*(n+1);
}
}
for (int i=1;i<n+1;++i)
if (nums[i-1]>=0) return i;
return n+1;
}
};