## 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 * 105
• -231 <= nums[i] <= 231 - 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:

1. Sanitize non-positive number: set all non-positive number to 0 so that they would not falsely represent an element with corresponding number.
2. 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
3. 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;
}
};