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;
};Dry Run
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.