First Missing Positive
Find smallest positive integer not present in the array.
Hard
Difficulty
O(n)
Time Complexity
O(1)
Space Complexity
Array Indices as Marker
Approach
Jan 18, 2026
Last Updated
Problem Statement
You are 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.
Examples
Example 1:
Input: nums = [-2,-1,0]
Output: 1
Example 2:
Input: nums = [1,2,4]
Output: 3
Example 3:
Input: [1,2,4,5,6,3,1]
Output: 7
Brute Force: Sorting
The easiest way to solve this problem is by sorting the array first. We know that the smallest positive integer is
When we find an element in the sorted array that is
1. Once the array is sorted, we declare a variable, say n = 1. Then when we find n in the sorted array, we increment n by 1.
When we find an element in the sorted array that is
greater than n, we know that the current value of n was the first missing positive integer. If we find no missing positives in the array at the end of the iteration, then the first missing positive would still be the current value of n.Brute Force approach using Sorting
FMPBruteForce.javaBrute Force approach using Sorting
1class FMPBruteForce {
2 public int firstMissingPositive(int[] nums) {
3
4 Arrays.sort(nums); // O(n.log n)
5 int n = 1;
6
7 for (int i=0; i<nums.length; i++){ // O(n)
8 if (nums[i] == n){
9 n++;
10 }
11 if (nums[i]>n){
12 return n;
13 }
14 }
15
16 return n;
17 }
18}Complexity Analysis
Time Complexity
Sorting Approach: O(n.log n)
Space Complexity
Sorting Approach: O(1)
Why it doesn't work
If sorting the array was allowed, then this would be tagged as an easy problem, but it's not. As the problem statement states, the time complexity must be
O(n) and space should be O(1). This solution is actually what makes this problem a hard.Mathematical Approach
Notice how no matter how complex the input numbers are, the smallest positive integer will always lie in the set and the length of the nums array .
Examples
Example 1:
Input: nums = [2,1,4]
Output: 3
Explanation: Length of nums is 3. So the missing number will always be in the range [1, 4]
Example 2:
Input: nums = [2,1,3]
Output: 4
Explanation: Length of nums is 3. So the missing number will always be in the range [1, 4]
Example 3:
Input: nums = [1, 11, 14]
Output: 1
Explanation: Even though we're now using bigger numbers, the missing positive still remains in the range of [1, 4]
Better Approach = HashSet
Using this newfound knowledge, we could initialize a hashset with the contents of
Since hashsets allows constant time access, we can directly search through the hashset from
Although we're now using extra space, we no longer need to sort the array, hence the time complexity now becomes
nums.
Since hashsets allows constant time access, we can directly search through the hashset from
n = [1 -> len(nums)] and find the element that's missing.
Although we're now using extra space, we no longer need to sort the array, hence the time complexity now becomes
O(n). We're now one step closer to the correct solution.Better Solution = using HashSet
FMPHashSet.javaBetter Solution = using HashSet
1class FMPHashSet {
2 public int firstMissingPositive(int[] nums) {
3
4 HashSet<Integer> set = new HashSet<>(); // space = O(n)
5
6 for (int i=0; i<nums.length; i++){ // time = O(n)
7 set.add(nums[i]);
8 }
9
10 int n = 1;
11
12 while (set.contains(n)){ // time = O(n)
13 n++;
14 }
15
16 return n;
17 }
18}Complexity Analysis
Time Complexity
Hashset Approach: O(n)
Space Complexity
Hashset Approach: O(n)
Best Solution = Mark indices
To solve this problem in O(n) time and O(1) space we need to use the input array itself.
We know that we're only looking for a positive integer, hence we have no need for the -ve integers in the array. So, we loop through the array and set all -ve integers to be zero.
Next we use the array indices to mark that an index is accounted for in the array. To do so, we have 4 conditions:
Once we've marked the indices, we loop through the value of n in the range [1, len(nums)] in nums, and if at any index, the number is +ve, that means it's associated index was not present in the array, hence the index+1 is the first missing positive in the array.
If we went through the entire array and found no missing indices, then len(nums)+1 becomes the first missing positive integer.
We know that we're only looking for a positive integer, hence we have no need for the -ve integers in the array. So, we loop through the array and set all -ve integers to be zero.
Next we use the array indices to mark that an index is accounted for in the array. To do so, we have 4 conditions:
- * For the number at nums[i] we mark the item at (i-1)th index in nums as negative, so mark the presence of the number in the array
- * If the nummber at nums[i-1] is already -ve at this point, it means we've already visited this index before, so we leave it as it is
- * If the number nums[i] is out of bounds for the set
[1, len(nums), again we do nothing and skip to the next number - * If the number nums[i-1] is a zero, which is an edge case, because we cannot set it as -ve, we set the number at nums[i-1] to be
nums[i]*(-1), to mark the index.
Once we've marked the indices, we loop through the value of n in the range [1, len(nums)] in nums, and if at any index, the number is +ve, that means it's associated index was not present in the array, hence the index+1 is the first missing positive in the array.
If we went through the entire array and found no missing indices, then len(nums)+1 becomes the first missing positive integer.
Optimal Approach = Use the input array indices as marker for number presence
FMP_Optimal.javaOptimal Approach = Use the input array indices as marker for number presence
1class FMP_Optimal {
2 public int firstMissingPositive(int[] nums) {
3
4 // replace all -ve values in nums to 0 since they are irrelevant
5 for (int i=0; i<nums.length; i++){
6 if (nums[i]<0){
7 nums[i] = 0;
8 }
9 }
10
11 // we know that, n = [1, len(nums)+1]
12
13 // for items i in nums
14 // mark nums[i-1] as -ve to mark the presence of the number in the array
15 // if nums[i-1] is out of bounds, ie, i<0 or i>len(nums), change nothing
16 // if nums[i-1] is already negative, change nothing
17 // if nums[i-1] is zero, update nums[i-1] to be (-1)*i
18 int index;
19 for (int i=0; i<nums.length; i++){
20 index = Math.abs(nums[i])-1;
21 if (index >= nums.length || index < 0){ // out of bounds
22 continue;
23 }
24 else if (nums[index] < 0){ // already -ve
25 continue;
26 }
27 else if (nums[index] == 0){ // there was a -ve no. at this index which is replaced by 0
28 nums[index] = (-1)*Math.abs(nums[i]);
29 }
30 else{ // mark the index
31 nums[index] = (-1)*nums[index];
32 }
33 }
34
35 int n;
36 // now go through the nums array again, and if you find a positive integer, that index+1 is the FMP
37 for (n = 1; n<=nums.length; n++){
38 if (nums[n-1]>=0) return n;
39 }
40
41 return n;
42 }
43}Complexity Analysis
Time Complexity
Input Array Indices: O(n)
Space Complexity
Input Array Indices: O(1)