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 - 1Problem Overview: Given an unsorted integer array, return the smallest missing positive integer. The challenge is achieving O(n) time while using O(1) extra space. Negative numbers and values larger than the array length must be ignored since they cannot affect the smallest missing positive within the range 1..n+1.
Approach 1: Hash Concept with Array (O(n) time, O(n) space)
This approach uses an auxiliary array or boolean marker structure to record which positive numbers appear in the input. First iterate through the array and mark presence for every number x where 1 ≤ x ≤ n. After marking, perform a second pass from index 1 to n to find the first index that was never marked. That index represents the smallest missing positive. The key insight is that the answer must lie within 1..n+1, so tracking only that range is sufficient. This method is simple and reliable but uses additional memory proportional to the input size, which violates the strict constant-space requirement often expected in interviews involving Hash Table style presence tracking.
Approach 2: Cyclic Sort (O(n) time, O(1) space)
The optimal approach places each number in its "correct" index using swaps. For an array of length n, the number x should ideally appear at index x-1. Iterate through the array and repeatedly swap elements until each valid number is either placed in its correct position or determined to be out of range. Only numbers between 1 and n participate in this placement step. After the rearrangement, perform a final pass: the first index i where nums[i] != i + 1 reveals the smallest missing positive. If every index is correct, the answer is n + 1. This technique relies on in-place swaps similar to cyclic sort, making it a classic Array manipulation problem that avoids extra memory.
The core insight is that the array itself can act as a hash structure. Instead of storing presence externally, you encode the presence of value x by placing it at position x-1. Each element moves at most once or twice, which keeps the total number of operations linear.
Recommended for interviews: The cyclic sort approach is the expected solution because it achieves O(n) time with O(1) extra space. Interviewers typically look for the realization that only numbers within 1..n matter and that the array can be rearranged to track presence. The hash-based approach demonstrates understanding of the problem constraints, but the in-place technique shows stronger mastery of array indexing tricks and space optimization.
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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Cyclic Sort | Time Complexity: O(n), as each number is swapped at most once. |
| Hash Concept with Array | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Concept with Array | O(n) | O(n) | When simplicity matters more than memory usage and extra space is allowed. |
| Cyclic Sort (In-place Index Placement) | O(n) | O(1) | Best for interviews or memory-constrained scenarios requiring constant extra space. |
First Missing Positive - Leetcode 41 - Python • NeetCode • 127,454 views views
Watch 9 more video solutions →Practice First Missing Positive with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor