First Missing Positive
Understanding the Problem
We need to find the smallest positive integer (1, 2, 3, ...) that doesn't appear in the array. Negative numbers, zeros, and duplicates do not affect the answer.
If the array has n elements, the answer must lie in the range [1, n+1]. With only n slots, the array can hold at most n distinct positive integers. If those happen to be exactly {1, 2, ..., n}, the answer is n+1. Otherwise at least one number in [1, n] is missing, and the smallest such number is the answer. The answer can never exceed n+1.
So we only care about values between 1 and n. Negatives, zeros, and numbers larger than n cannot be the answer, and they free up the values we do care about to be tracked inside the array itself. That range bound is what makes the O(1) space solution possible.
Key Constraints:
1 <= nums.length <= 10^5→ With up to 100,000 elements, an O(n^2) scan would mean 10^10 operations, too slow. We need O(n log n) or better.-2^31 <= nums[i] <= 2^31 - 1→ Values can be negative, zero, or as large asINT_MAX. Any approach that indexes by value must first check that the value falls in[1, n], otherwise it would index out of bounds or overflow.- The problem requires O(n) time and O(1) auxiliary space → This rules out the hash set (O(n) space) and sorting (O(n log n) time). The optimal solution rearranges the input array in place.
Approach 1: Hash Set
Intuition
Put every number into a hash set, then check 1, 2, 3, ... in order until one is not in the set. The hash set gives O(1) membership lookups, so each check is constant time.
This uses O(n) extra space, so it does not meet the O(1) requirement. It is a clean baseline that makes the range bound concrete before we optimize the space away.
Algorithm
- Add all elements from
numsinto a hash set. - Starting from 1, check if each positive integer exists in the set.
- Return the first positive integer not found in the set.
Example Walkthrough
Code
- Time Complexity: O(n). Building the hash set takes O(n). Checking integers 1 through n+1 takes O(n) in the worst case, with each check being O(1). Total is O(n).
- Space Complexity: O(n). The hash set stores up to n elements.
The hash set costs O(n) extra space. The next approach removes that extra space by sorting the array in place and scanning for the first gap in the positive sequence.
Approach 2: Sorting
Intuition
After sorting, the positive integers appear in ascending order. Walk through the sorted array tracking the next positive integer we expect to see, starting at 1. The first expected value that does not appear is the answer.
Sorting trades time (O(n log n)) for space (O(1) with an in-place sort), the opposite trade-off from the hash set. Neither is optimal, but the sorted order makes the gap easy to spot.
Algorithm
- Sort the array in ascending order.
- Initialize
expected = 1(the first positive integer we're looking for). - Iterate through the sorted array:
- Skip negative numbers, zeros, and duplicates.
- If the current number equals
expected, incrementexpected. - If the current number is greater than
expected, we found the gap. - Return
expected.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting dominates the cost. The scan afterward is O(n).
- Space Complexity: O(1) or O(log n). Depends on the sorting algorithm. In-place sorts like heapsort use O(1), but most standard library sorts use O(log n) for the recursion stack.
Sorting reaches O(1) space but costs O(n log n) time. We do not need the array fully sorted, only each value placed at its own index. The next approach does exactly that in linear time, placing each value v in [1, n] directly at index v-1.
Approach 3: Cyclic Sort (Optimal)
Intuition
The input array can serve as its own hash map. Since the answer is in [1, n+1], we only need to know which values from 1 to n are present, and the array has exactly n slots to record that.
Place each value v in [1, n] at index v-1: value 1 goes to index 0, value 2 to index 1, and so on. After this rearrangement, the answer is a single scan away: the first index i where nums[i] != i + 1 means i + 1 is missing.
The rearrangement is done with cyclic sort. For each index, repeatedly swap the current element toward its correct index, stopping when the element is out of range (negative, zero, or greater than n), already in its correct index, or its target index already holds the same value (a duplicate).
Algorithm
- For each index
ifrom 0 to n-1: - While
nums[i]is in range [1, n] andnums[i]is not in its correct position: - Swap
nums[i]withnums[nums[i] - 1](put it where it belongs). - Scan the array: return the first
i + 1wherenums[i] != i + 1. - If all positions are correct, return
n + 1.
Example Walkthrough
Code
Every swap moves a value into the index where it belongs, and a value that reaches its correct index is never moved again. There are n indices, so the total number of swaps across the entire run is at most n. The while loop can iterate many times for a single i, but those iterations are charged against the n swaps available overall, not against i. So the nested loop runs in O(n) total, not O(n^2).
The condition nums[nums[i] - 1] != nums[i] is what stops the loop on a duplicate. If the target index already holds the same value, swapping would exchange two equal values forever. Comparing values instead of indices means a second copy of value v is left in place once the first copy has claimed index v-1.
- Time Complexity: O(n). Each element is swapped at most once to its correct position, so the total swaps across all iterations is bounded by n. The final scan is another O(n). Total: O(n).
- Space Complexity: O(1). We only use a few variables for swapping. The rearrangement happens in-place.