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 - 1The key challenge in First Missing Positive is finding the smallest missing positive integer in O(n) time while using O(1) extra space. Since the answer must lie in the range 1 to n + 1 (where n is the array length), we can leverage the array itself to track which numbers exist.
A common strategy is an index placement (cyclic sort–style) approach. The idea is to place each value x at index x - 1 whenever 1 ≤ x ≤ n. By repeatedly swapping elements into their correct positions, the array becomes a representation of which positives are present. A final scan reveals the first index where nums[i] != i + 1, which corresponds to the missing positive.
An alternative approach uses a hash set to record all positive numbers and then checks sequentially from 1 upward. While simpler conceptually, it requires additional memory. The in-place method is preferred in interviews because it achieves O(n) time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-place index placement (cyclic positioning) | O(n) | O(1) |
| Hash Set tracking | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
We don't care about duplicates or non-positive integers
Remember that O(2n) = O(n)
This approach utilizes the cyclic sort algorithm to place numbers in their corresponding indices. For example, 1 should be at index 0, 2 should be at index 1, etc. While rearranging, we ignore numbers outside the range [1, n], where n is the length of the array.
After rearranging, the first index i that doesn’t have a number i+1 indicates the smallest missing positive integer.
Time Complexity: O(n), as each number is swapped at most once.
Space Complexity: O(1), as no additional space is used apart from variables.
1#include <stdio.h>
2
3int firstMissingPositive(int* nums, int numsSize) {
4 for (int i = 0; i < numsSize;
The function iterates over the array, swapping elements within the valid range to their correct positions. It then checks for the first missing positive by assessing incorrect positions.
By assuming the input array itself can act like a hash map, this approach assigns each index with a corresponding positive value within the range. If out of range, we fill that index with a placeholder number like the array size + 1.
We then use index signs to mark present numbers and deduce the missing positive from the invalid marked position.
Time Complexity: O(n)
Space Complexity: O(1)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If an array has length n, it can contain at most n distinct positive numbers from the range 1 to n. If all numbers from 1 to n appear, the smallest missing positive must be n+1. This observation helps narrow the search space and enables efficient solutions.
Yes, First Missing Positive is a well-known hard interview problem and has appeared in FAANG-style interviews. It tests array manipulation, index mapping, and the ability to design in-place algorithms with strict time and space constraints.
The most efficient solution relies directly on the input array as a placement structure rather than using additional data structures. However, a hash set can also be used to track seen positive numbers, which simplifies the logic but requires O(n) extra space.
The optimal approach rearranges elements so each number x is placed at index x-1 when possible. After this in-place placement, a linear scan identifies the first index where the value does not match its expected position. This achieves O(n) time and O(1) extra space.
Remove out of range numbers by filling them with the max possible value. Using negative marking helps identify seen numbers within the range, returning the first positive marked index.