Find the First Absent Positive Integer
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The integer array `values` is unsorted and may include repeated values, zeroes, and negative numbers. Return the first absent positive integer: the smallest integer greater than zero that does not occur in the array.
For an array of length `n`, your implementation must take `O(n)` time and use only `O(1)` auxiliary space.
### Examples
**Example 1**
```text
Input: values = [-4,2,1,2,5]
Output: 3
```
Both `1` and `2` occur, but `3` is absent. Repeating `2` does not change which positive integers are present.
**Example 2**
```text
Input: values = [2,3,4]
Output: 1
```
The first positive integer is already missing.
### Constraints
- `1 <= values.length <= 10^5`
- `-2^31 <= values[i] <= 2^31 - 1`
Overview: Find the smallest absent positive integer in an unsorted array with duplicates and negative values, using linear time and constant auxiliary space.
