# 41. First Missing Positive

Reference: LeetCode
Difficulty: Hard

## Problem

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

Example:

Follow up: Your algorithm should run in $O(n)$ time and uses constant extra space.

## Analysis

Basic Idea: Since there are only n spaces in the array, we have the follow different cases (n = 5):

• [1, 2, 3, 4, 5]: Return 6. (n + 1)
• [1, 2, 2, 4, 5]: Return 3. ([1, n])
• [1, 2, -1, 2, 5]: Return 3. ([1, n])

The invariant is that the smallest positive integer must be in the interval [1, n + 1].

### Brute-Force

For each value in [1, n], check if it is in nums.

• If it does not exist, return the corresponding index i.
• If all values in [1, n] exist in the array, return n + 1.

Time: $O(N^2)$
Space: $O(1)$

### Hash Set

The brute-force approach could be optimized by using a hash set.

Time: $O(N)$
Space: $O(N)$

### In-place Optimization

We can actually use the values in the array to indicate if the values from 1 to n exists.

For example, since 3 exists, we set the value (-1) at 3 - 1 to negative.

Before this process, we should traverse the array, setting all non-positive numbers and out-of-bound numbers to 1. In the above example, the output of preprocessing will be [3, 4, 1, 1].

Since we set those values to 1, during the first iteration, we must check if 1 exists. If it does not exist, the result is going to be 1. No further action should be made.

Then we process the array [3, 4, 1, 1], the output is [-3, 4, -1, -1]. In the final pass, we find that 4 is positive. So the element is the index of 4 plus one, which is 2.

Note: When using val as index, remember to use the absolute value because it might be set to negative in advance.

Time: $O(N)$
Space: $O(1)$

Comment
Junhao Wang
a software engineering cat