## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - First Missing Positive

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/first-missing-positive

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 <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
``````

### Explanation

#### Brute force approach

The naive approach is to run two nested for loops and identify the first missing positive integer. The maximum positive number in an array of size n will be n + 1.

The outer for loop starts from 1 and ends at n + 1. We linearly search from 1 to n + 1 in the array. If any positive integer is missing in the sequence, we will return that value.

The C++ snippet of the above approach is as follows:

``````int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
bool missingNumber = false;

for (int i = 1; i <= n + 1; i = i + 1) {
missingNumber = true;

for (int j = 0; j < n; j = j + 1) {
if (nums[j] == i) {
missingNumber = false;
break;
}
}

if(missingNumber)
return i;
}
}
``````

The time complexity of this approach is O(n^2). We are not using any additional space, so the space complexity is O(1).

#### Sorting

We can optimize the time complexity using sorting. We first sort the array using QuickSort or HeapSort. Then we iterate over the array linearly to find the first missing positive integer.

The C++ snippet of this approach is as follows:

``````int firstMissingPositive(vector<int>& nums) {
sort(nums.begin(), nums.end())
int n = nums.size(), i = 0;

while(nums[i] <  1) {
i++;
}

int missingNumber = 1;

for(int j = i; j < n; j++) {
if(missingNumber == nums[j]) {
missingNumber += 1;
} else if(missingNumber < nums[j]) {
return missingNumber;
}
}

return missingNumber;
}
``````

As we are sorting the array the time complexity of this approach is O(n * log(n)). The space complexity is O(1).

#### Hash Table

We can further improve the time complexity of our approach by using a hash table. We create a hash table for size n. We run a loop over the array and insert all the elements in the hash. We run another loop from 1 to n + 1. If any element i is not present in the hash table we return i.

The C++ snippet of this approach is as follows:

``````int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
map<int, int> m;
int i = 0;

while( i < n) {
m[nums[i]] = i;
}

for(int i = 1; i <= n + 1; i++) {
if(m.find(i) == m.end()) {
return i;
}
}

return n + 1;
}
``````

We are scanning the array and map linearly the time complexity of this approach is O(n). As we are using an additional space in terms of the hash table, the space complexity is O(n).

#### Optimized solution

We can solve this problem without using any additional place. We use the array indexes to mark the presence of the numbers in the array. We mark the number X at nums[X - 1]. The number 1 gets placed at nums[0], 2 at nums[1], and so on. We don't mark numbers that are negative or greater than n + 1.

Let's check the algorithm first.

#### Algorithm

``````- set i = 0
n = nums.size()

- loop while i < n
- if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
- swap nums[nums[i] - 1] and nums[i]
- else
- increment i: i++
- if end
- while end

- loop for i = 0; i < n; i++
- if nums[i] != i + 1
- return i + 1
- if end
- for end

- return n + 1
``````

The time complexity of this approach is O(n). The space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

#### C++ solution

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int i = 0, n = nums.size();

while(i < n) {
if(nums[i] > 0 & nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
} else {
i++;
}
}

for(i = 0; i < n; i++) {
if(nums[i] != i + 1) {
return i + 1;
}
}

return n + 1;
}
};
``````

#### Golang solution

``````func firstMissingPositive(nums []int) int {
i, n := 0, len(nums)
tmp := 0

for i < n {
if nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
tmp = nums[nums[i] - 1]
nums[nums[i] - 1] = nums[i]
nums[i] = tmp
} else {
i++
}
}

for i = 0; i < n; i++ {
if nums[i] != i + 1 {
return i + 1
}
}

return n + 1
}
``````

#### JavaScript solution

``````var firstMissingPositive = function(nums) {
let i = 0, n = nums.length;
let tmp;

while(i < n) {
if(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
tmp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = tmp;
} else {
i++;
}
}

for(i = 0; i < n; i++) {
if(nums[i] != i + 1) {
return i + 1;
}
}

return n + 1;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: nums = [3, 4, -1, 1]

Step 1: i = 0
n = nums.size()
= 4

Step 2: loop while i < n
0 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[0] > 0 && nums[0] <= 4 + 1 && nums[nums[0] - 1] != nums[0]
3 > 0 && 3 <= 5 && nums[3 - 1] != 3
true && true && nums[2] != 3
true && -1 != 3
true

swap(nums[nums[i] - 1], nums[i])
swap(nums[2], nums[0])

nums = [-1, 4, 3, 1]

while continue

while i < n
0 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[0] > 0 && nums[0] <= 4 + 1 && nums[nums[0] - 1] != nums[0]
-1 > 0
false

else
i++
i = 1

while i < n
1 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[1] > 0 && nums[1] <= 4 + 1 && nums[nums[1] - 1] != nums[1]
4 > 0 && 4 <= 5 && nums[4 - 1] != 4
true && true && nums[3] != 4
true && 1 != 3
true

swap(nums[nums[i] - 1], nums[i])
swap(nums[3], nums[1])

nums = [-1, 1, 3, 4]

while continue

while i < n
1 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[1] > 0 && nums[1] <= 4 + 1 && nums[nums[1] - 1] != nums[1]
1 > 0 && 1 <= 5 && nums[1 - 1] != 1
true && true && nums[0] != 1
true && -1 != 1
true

swap(nums[nums[i] - 1], nums[i])
swap(nums[0], nums[1])

nums = [1, -1, 3, 4]

while continue

while i < n
1 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[1] > 0 && nums[1] <= 4 + 1 && nums[nums[1] - 1] != nums[1]
-1 > 0
false

else
i++
i = 2

while i < n
2 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[2] > 0 && nums[2] <= 4 + 1 && nums[nums[2] - 1] != nums[2]
3 > 0 && 3 <= 5 && nums[3 - 1] != nums[2]
true && true && nums[2] != nums[2]
false

else
i++
i = 3

while i < n
3 < 4
true

if nums[i] > 0 && nums[i] <= n + 1 && nums[nums[i] - 1] != nums[i]
nums[3] > 0 && nums[3] <= 4 + 1 && nums[nums[3] - 1] != nums[3]
4 > 0 && 4 <= 5 && nums[4 - 1] != nums[3]
true && true && nums[3] != nums[3]
false

else
i++
i = 4

while i < n
4 < 4
false

Step 3: loop for i = 0; i < n
0 < 4
true

if nums[i] != i + 1
nums[0] != 0 + 1
1 != 1
false

i++
i = 1

loop for i < n
1 < 4
true

if nums[i] != i + 1
nums[1] != 1 + 1
-1 != 2
true

return i + 1

We return the answer as 2.
``````