## Problem

**Problem ID**: 41

**Title**: First Missing Positive

**Difficulty**: Hard

**Description**:

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.

**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:**

`1 <= nums.length <= 5 * 10`

^{5}`-2`

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

## Thoughts

This is an interesting problem that utilises discreet math.

## Solution

**General Idea**

Key Observations:

- By pigeon hole principal, the answer must be
`1 <= Ans <= N + 1`

. Each positive number is assigned the element`num - 1`

. In the worst case scenario all elements in the vector are assigned a number and`Ans = N+1`

otherwise the answer is the first element that does not have a corresponding number. - All non-positive numbers will not affect the answer and can be modified to any number that is non-positive or already in the set (can set as a flag).

Intuition: each valid number (`1 <= num <= N`

) will be assigned to the element
`num - 1`

. For each element, if there is a corresponding number then the value is `< 0`

.
Finally iterate through all the elements, if any of the element is not `< 0`

then return the index
as the answer.

Algorithm:

- Sanitize non-positive number: set all non-positive number to
`0`

so that they would not falsely represent an element with corresponding number. - For each absolute value of the number that is valid (
`!= 0 && <= N`

), set the value to negative.- Absolute: the number could be negative when a separate number that corresponding to that element it is on is present

- Iterate through all elements and find the first element that is negative. That index represent the answer.

### Implementation

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