# First Missing Positive
**Difficulty:** HARD
[External](https://leetcode.com/problems/first-missing-positive)
Canonical: https://scaleengineer.com/dsa/problems/first-missing-positive
**Data structures:** Array, Hash Table
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Myntra](https://scaleengineer.com/companies/myntra), [Nutanix](https://scaleengineer.com/companies/nutanix), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [athenahealth](https://scaleengineer.com/companies/athenahealth), [eBay](https://scaleengineer.com/companies/ebay), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Swiggy](https://scaleengineer.com/companies/swiggy), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Geico](https://scaleengineer.com/companies/geico), [Zomato](https://scaleengineer.com/companies/zomato), [Twilio](https://scaleengineer.com/companies/twilio), [Celigo](https://scaleengineer.com/companies/celigo), [General Motors](https://scaleengineer.com/companies/general-motors), [Licious](https://scaleengineer.com/companies/licious), [SoundHound](https://scaleengineer.com/companies/soundhound), [Sumo Logic](https://scaleengineer.com/companies/sumo-logic)
---
## Problem
Given an unsorted integer array `nums`. Return the _smallest positive integer_ that is _not present_ in `nums`.

You must implement an algorithm that runs in `O(n)` time and uses `O(1)` auxiliary space.

**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 <= 105`
* `-231 <= nums[i] <= 231 - 1`

# Approaches
## Sorting Approach
This approach involves sorting the array first. A sorted array makes it easy to find the first missing positive integer by simply iterating through it and checking for a gap in the sequence of positive numbers.
**Time:** O(n log n) · **Space:** O(log n) to O(n)
**Pros:** The logic is straightforward and easy to implement.
**Cons:** The time complexity does not meet the problem's requirement of `O(n)`.
### Explanation
The algorithm begins by sorting the input array `nums`. Once sorted, we can perform a single linear scan to find the first gap in the sequence of positive integers starting from 1. We use a variable, say `expectedPositive`, initialized to 1. As we iterate through the sorted array, we compare each positive number with `expectedPositive`. If the current number matches `expectedPositive`, we increment `expectedPositive` to look for the next integer in the sequence. If we encounter a number that is greater than `expectedPositive`, we have found our gap, and `expectedPositive` is the smallest missing positive. We must also handle duplicates and non-positive numbers by skipping them appropriately. If we traverse the entire array, the answer is the final value of `expectedPositive`.

For example, if `nums = [3, 4, -1, 1]`, sorting gives `[-1, 1, 3, 4]`. We expect `1`, we find it, so we now expect `2`. The next positive number is `3`, which is greater than `2`. Thus, `2` is the answer.

```java
import java.util.Arrays;

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int expectedPositive = 1;
        for (int num : nums) {
            if (num > 0) {
                if (num == expectedPositive) {
                    expectedPositive++;
                } else if (num > expectedPositive) {
                    return expectedPositive;
                }
                // If num < expectedPositive, it's a duplicate or a smaller number
                // that has already been accounted for. We just ignore it.
            }
        }
        return expectedPositive;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a variable, `expectedPositive`, to `1`.
- Iterate through the sorted array. For each number `num`:
  - If `num` is positive:
    - If `num` is equal to `expectedPositive`, we've found the number we were looking for, so we increment `expectedPositive`.
    - If `num` is greater than `expectedPositive`, it means `expectedPositive` is missing. Return `expectedPositive`.
    - If `num` is less than `expectedPositive`, it's a duplicate of a number we've already processed, so we do nothing.
- If the loop completes, it means all integers from `1` up to the last found positive were present. The answer is the final value of `expectedPositive`.

## Using a Hash Set
This approach uses a hash set to store all the positive numbers from the input array. This allows for constant-time lookups to check for the existence of a number. We can then iterate from 1 upwards to find the first integer that is not in the set.
**Time:** O(n) · **Space:** O(n)
**Pros:** Achieves the required `O(n)` time complexity.; The logic is relatively simple to follow.
**Cons:** Uses `O(n)` auxiliary space, which violates the `O(1)` space constraint of the problem.
### Explanation
To achieve a linear time solution, we can use extra space in the form of a hash set. The algorithm first populates a `HashSet` with all the positive integers from the `nums` array. This step takes `O(n)` time as we iterate through the array once, and hash set insertion is, on average, an `O(1)` operation.

After building the set, we need to find the first missing positive. We know the answer must lie in the range `[1, n+1]`, where `n` is the number of elements in the array. So, we simply loop from `i = 1` to `n + 1` and use the hash set to check for the presence of each `i`. The first `i` that is not in the set is our result. This second loop also runs in `O(n)` time.

For instance, with `nums = [3, 4, -1, 1]`, the set becomes `{1, 3, 4}`. We then check for `1` (present), then `2` (not present), so we return `2`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (num > 0) {
                set.add(num);
            }
        }
        
        int n = nums.length;
        for (int i = 1; i <= n + 1; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Create a `HashSet` to store positive integers.
- Iterate through the input array `nums`. For each number, if it's positive, add it to the hash set.
- Let `n` be the length of the array.
- Iterate from `i = 1` up to `n + 1`.
- In each iteration, check if `i` is present in the hash set.
- The first integer `i` that is not found in the set is the smallest missing positive. Return `i`.

## In-place Hashing (Cyclic Sort)
This optimal approach cleverly uses the array itself as a hash map to achieve `O(n)` time and `O(1)` space complexity. The idea is to place each number `x` in its correct position, which is the index `x-1`. After rearranging the array, a single pass can find the first missing positive.
**Time:** O(n) · **Space:** O(1)
**Pros:** Extremely efficient, meeting both `O(n)` time and `O(1)` space constraints.; Provides an optimal solution to the problem.
**Cons:** The in-place manipulation can be less intuitive and trickier to implement correctly compared to other approaches.
### Explanation
This approach meets both time and space constraints by modifying the array in-place. The core idea is that the first missing positive must be in the range `[1, n+1]`. We can therefore use the array's indices `0` to `n-1` to signify the presence of numbers `1` to `n`.

The algorithm works in two phases. In the first phase, we iterate through the array and place each number in its correct position. For a number `x`, its correct position is index `x-1`. So, for each `nums[i]`, if it's a number between `1` and `n` and it's not already at `nums[nums[i]-1]`, we swap it. We repeat this for the element at index `i` until it holds a number that doesn't belong in the `[1, n]` range or is already in its correct spot. Despite the nested loop appearance, the total number of swaps is at most `n`, making this phase `O(n)`.

In the second phase, we iterate through the modified array. The first index `i` where `nums[i]` is not equal to `i+1` reveals that `i+1` is the first missing positive. If we iterate through the whole array and find no such mismatch, it means all numbers from `1` to `n` are present, and the answer must be `n+1`.

```java
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Phase 1: Place each number in its correct spot
        int i = 0;
        while (i < n) {
            int correctIndex = nums[i] - 1;
            if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
                // Swap nums[i] with the element at its correct index
                int temp = nums[i];
                nums[i] = nums[correctIndex];
                nums[correctIndex] = temp;
            } else {
                i++;
            }
        }

        // Phase 2: Find the first missing positive
        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // If all numbers from 1 to n are present
        return n + 1;
    }
}
```
### Algorithm
- **Phase 1: Rearrangement**
  - Iterate through the array with an index `i` from `0` to `n-1`.
  - For each element `nums[i]`, as long as it's a valid number (`1 <= nums[i] <= n`) and it's not in its correct place (`nums[i] != nums[nums[i] - 1]`), swap it with the element at its correct index (`nums[i] - 1`).
  - This process, often called Cyclic Sort, places each number `x` at index `x-1` if possible.
- **Phase 2: Find Missing**
  - Iterate through the rearranged array from `i = 0` to `n-1`.
  - The first index `i` where `nums[i] != i + 1` indicates that `i + 1` is the smallest missing positive. Return `i + 1`.
- If the second loop completes without returning, it means all numbers from `1` to `n` are present. The answer is `n + 1`.

# Solutions
### CSharp

```csharp
public class Solution { public int FirstMissingPositive ( int [] nums ) { var i = 0 ; while ( i < nums . Length ) { if ( nums [ i ] > 0 && nums [ i ] <= nums . Length ) { var index = nums [ i ] - 1 ; if ( index != i && nums [ index ] != nums [ i ]) { var temp = nums [ i ]; nums [ i ] = nums [ index ]; nums [ index ] = temp ; } else { ++ i ; } } else { ++ i ; } } for ( i = 0 ; i < nums . Length ; ++ i ) { if ( nums [ i ] != i + 1 ) { return i + 1 ; } } return nums . Length + 1 ; } }
```

### Java

```java
class Solution {
public
  int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i + 1 != nums[i]) {
        return i + 1;
      }
    }
    return n + 1;
  }
private
  void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int firstMissingPositive(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
        swap(nums[i], nums[nums[i] - 1]);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (i + 1 != nums[i]) {
        return i + 1;
      }
    }
    return n + 1;
  }
};

```

### Python

```python
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int: def swap(i, j): nums[i], nums[j] = nums[j], nums[i] n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]: swap(i, nums[i] - 1) for i in range(n): if i + 1 != nums[i]: return i + 1 return n + 1

```