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: You are given an unsorted integer array. The goal is to find the smallest positive integer that does not appear in the array. The challenge is handling negative numbers, duplicates, and large values while keeping the solution efficient.
Approach 1: Sorting the Array (O(n log n) time, O(1) extra space)
A straightforward strategy is to sort the array first, then scan from left to right looking for the first gap in positive integers. After sorting, maintain a variable representing the smallest expected positive value starting at 1. Iterate through the array and update this expected value whenever you encounter it. When the expected number is skipped, that value is the missing positive. This approach is simple to reason about but sorting introduces O(n log n) time complexity, which is slower than the optimal linear solution.
Approach 2: Hash Concept with Array (O(n) time, O(n) space)
This method uses a boolean array or hash-based presence tracking. Create a structure of size n + 1 (where n is the input size) and mark whether each positive number in the range [1, n] appears in the input. Iterate through the original array and mark valid numbers. Then scan the tracking array starting from index 1; the first unmarked index is the missing positive. Any number larger than n can be ignored because the answer must fall within [1, n+1]. This technique relies on constant-time hash lookups and sequential iteration, producing O(n) time complexity but requiring additional memory.
Approach 3: Cyclic Sort / Index Placement (O(n) time, O(1) space)
The optimal approach uses an index-placement idea often associated with cyclic sort. Since the smallest missing positive must lie in the range [1, n+1], each value x ideally belongs at index x - 1. Iterate through the array and repeatedly swap elements so that valid numbers are placed at their correct indices. For example, if the current value is 3, swap it with the element at index 2. Continue swapping until the current number is either out of range, already positioned correctly, or a duplicate. After this placement pass, run another scan: the first index i where nums[i] != i + 1 reveals the missing positive i + 1. If all positions are correct, the answer is n + 1. This method modifies the array in-place and achieves O(n) time with O(1) extra space.
Recommended for interviews: The cyclic sort approach is the one most interviewers expect because it satisfies the strict constraints of O(n) time and constant extra space. Starting with the hash-based method demonstrates clear reasoning about the range of possible answers, but recognizing that the array itself can act as the storage structure shows deeper algorithmic skill. Problems like this commonly appear in discussions around array manipulation and hash table style presence tracking.
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.
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.
Time Complexity: O(n)
Space Complexity: O(1)
We assume the length of the array nums is n, then the smallest positive integer must be in the range [1, .., n + 1]. We can traverse the array and swap each number x to its correct position, that is, the position x - 1. If x is not in the range [1, n + 1], then we can ignore it.
After the traversal, we traverse the array again. If i+1 is not equal to nums[i], then i+1 is the smallest positive integer we are looking for.
The time complexity is O(n), where n is the length of the array. The space complexity is 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) |
| In-place Swap | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) | Quick baseline solution when optimal constraints are not required |
| Hash Concept with Array | O(n) | O(n) | Simple linear solution using presence tracking |
| Cyclic Sort (Index Placement) | O(n) | O(1) | Best interview solution when constant extra space is required |
First Missing Positive - Leetcode 41 - Python • NeetCode • 160,037 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