.png)
Find the First Missing Positive Integer
Problem Statement
You are given an unsorted integer array arr.
Find the smallest missing positive integer.
You must solve this problem in O(n) time and O(1) extra space.
Example 1
Input
arr = [1, 2, 0]
Output
3
Explanation
Positive integers present are 1 and 2.
The smallest missing positive is 3.
Example 2
Input
arr = [3, 4, -1, 1]
Output
2
Example 3
Input
arr = [7, 8, 9, 11, 12]
Output
1
Why This Problem Is Important
- Extremely frequent interview question
- Asked in FAANG & top product companies
- Tests array manipulation
- Requires index mapping logic
- Enforces O(n) time & O(1) space
- Strong test of in-place algorithms
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Sorting | O(n log n) | O(1) |
| Approach 2 | Hashing | O(n) | O(n) |
| Approach 3 | Index Mapping (Optimal) | O(n) | O(1) |
Approach 1: Sorting
Idea
Sort the array and check the smallest missing positive sequentially.
Algorithm
- Sort the array
- Initialize expected = 1
- Traverse array
- If current element equals expected, increment it
- Ignore negatives & duplicates
Time & Space Complexity
- Time: O(n log n)
- Space: O(1)
Implementations
C
#include
#include
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int arr[] = {3,4,-1,1};
int n = 4;
qsort(arr, n, sizeof(int), cmp);
int expected = 1;
for(int i = 0; i < n; i++) {
if(arr[i] == expected)
expected++;
}
printf("%d", expected);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
int arr[] = {3,4,-1,1};
int n = 4;
sort(arr, arr + n);
int expected = 1;
for(int i = 0; i < n; i++) {
if(arr[i] == expected)
expected++;
}
cout << expected;
return 0;
}
Java
import java.util.*;
public class FirstMissingPositive {
public static void main(String[] args) {
int[] arr = {3,4,-1,1};
Arrays.sort(arr);
int expected = 1;
for(int x : arr) {
if(x == expected)
expected++;
}
System.out.print(expected);
}
}
Python
arr = [3,4,-1,1]
arr.sort()
expected = 1
for x in arr:
if x == expected:
expected += 1
print(expected)
JavaScript
let arr = [3,4,-1,1];
arr.sort((a,b) => a-b);
let expected = 1;
for (let x of arr) {
if (x === expected)
expected++;
}
console.log(expected);
Approach 2: Hashing
Idea
Store all positive numbers in a set and find the first missing one.
Algorithm
- Insert all positive numbers into a HashSet
- Start checking from 1 upwards
- First missing number is the answer
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {3,4,-1,1};
int n = 4;
unordered_set s;
for(int i = 0; i < n; i++) {
if(arr[i] > 0)
s.insert(arr[i]);
}
int missing = 1;
while(s.count(missing))
missing++;
cout << missing;
return 0;
}
Java
import java.util.*;
public class FirstMissingPositive {
public static void main(String[] args) {
int[] arr = {3,4,-1,1};
HashSet set = new HashSet<>();
for(int x : arr)
if(x > 0)
set.add(x);
int missing = 1;
while(set.contains(missing))
missing++;
System.out.print(missing);
}
}
Python
arr = [3,4,-1,1]
s = set(x for x in arr if x > 0)
missing = 1
while missing in s:
missing += 1
print(missing)
JavaScript
let arr = [3,4,-1,1];
let set = new Set(arr.filter(x => x > 0));
let missing = 1;
while (set.has(missing))
missing++;
console.log(missing);
Approach 3: Index Mapping (Optimal)
Idea
Place each number x at index x - 1.
Then find the first index where this condition fails.
Algorithm
- For each index i
- While arr[i] is in range [1, n]
- Swap it to correct position
- Traverse array
- First index i where arr[i] != i + 1
- Return i + 1
Time & Space Complexity
- Time: O(n)
- Space: O(1)
Implementations
C
#include
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int main() {
int arr[] = {3,4,-1,1};
int n = 4;
for(int i = 0; i < n; i++) {
while(arr[i] >= 1 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
swap(&arr[i], &arr[arr[i] - 1]);
}
}
for(int i = 0; i < n; i++) {
if(arr[i] != i + 1) {
printf("%d", i + 1);
return 0;
}
}
printf("%d", n + 1);
return 0;
}
C++
#include
using namespace std;
int main() {
int arr[] = {3,4,-1,1};
int n = 4;
for(int i = 0; i < n; i++) {
while(arr[i] >= 1 && arr[i] <= n && arr[arr[i]-1] != arr[i])
swap(arr[i], arr[arr[i]-1]);
}
for(int i = 0; i < n; i++) {
if(arr[i] != i + 1) {
cout << i + 1;
return 0;
}
}
cout << n + 1;
return 0;
}
Java
public class FirstMissingPositive {
public static void main(String[] args) {
int[] arr = {3,4,-1,1};
int n = arr.length;
for(int i = 0; i < n; i++) {
while(arr[i] >= 1 && arr[i] <= n && arr[arr[i]-1] != arr[i]) {
int temp = arr[i];
arr[i] = arr[temp - 1];
arr[temp - 1] = temp;
}
}
for(int i = 0; i < n; i++) {
if(arr[i] != i + 1) {
System.out.print(i + 1);
return;
}
}
System.out.print(n + 1);
}
}
Python
arr = [3,4,-1,1]
n = len(arr)
for i in range(n):
while 1 <= arr[i] <= n and arr[arr[i] - 1] != arr[i]:
arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1]
for i in range(n):
if arr[i] != i + 1:
print(i + 1)
break
else:
print(n + 1)
JavaScript
let arr = [3,4,-1,1];
let n = arr.length;
for (let i = 0; i < n; i++) {
while (arr[i] >= 1 && arr[i] <= n && arr[arr[i] - 1] !== arr[i]) {
[arr[i], arr[arr[i] - 1]] = [arr[arr[i] - 1], arr[i]];
}
}
for (let i = 0; i < n; i++) {
if (arr[i] !== i + 1) {
console.log(i + 1);
return;
}
}
console.log(n + 1);
Dry Run (Optimal Approach)
Input
[3, 4, -1, 1]
After placement:
[1, -1, 3, 4]
Index 1 should contain 2 → missing is 2
Summary
- Sorting & Hashing are intuitive but not optimal
- Index mapping solves in O(n) time & O(1) space
- This is the interview-preferred solution
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
