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 are irrelevant to our answer.

Here's the critical observation: if the array has n elements, the answer must be somewhere in the range [1, n+1]. Why? In the best case, the array contains exactly {1, 2, 3, ..., n}, and the answer is n+1. In any other case, at least one number in [1, n] is missing, and the answer is that missing number.

This means we only care about values between 1 and n. Everything else (negatives, zeros, numbers bigger than n) can be ignored. That observation is what makes the O(1) space solution possible.

Key Constraints:

1 <= nums.length <= 10^5 → With up to 100,000 elements, O(n^2) would mean 10^10 operations, which is too slow. We need O(n log n) or better.
-2^31 <= nums[i] <= 2^31 - 1 → Values can be negative, zero, or very large. We need to handle out-of-range values gracefully without integer overflow.
The problem explicitly requires O(n) time and O(1) auxiliary space → This eliminates hash sets (O(n) space) and sorting (O(n log n) time). We need an in-place technique.

Approach 1: Hash Set

Intuition

The simplest way to solve this is to throw all the numbers into a hash set, then check 1, 2, 3, ... until we find one that's missing. The hash set gives us O(1) lookups, so each check is fast.

This doesn't meet the O(1) space requirement, but it's a great starting point for understanding the problem and building toward the optimal solution.

Algorithm

Add all elements from nums into 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

1Initialize: add all elements to hash set. Set = {3, 4, -1, 1}

-1

1/3

Code

Complexity Analysis

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.

This approach works but uses O(n) extra space for the hash set. What if we sorted the array instead and scanned for the first gap in the positive sequence?

Approach 2: Sorting

Intuition

If we sort the array first, all the positive integers will be grouped together in ascending order. We can then walk through the sorted array and find where the sequence of positive integers breaks.

Sorting trades time (O(n log n)) for space (O(1) if using an in-place sort), which is the opposite trade-off from the hash set approach. Neither is optimal, but sorting reveals the structure of the problem nicely.

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, increment expected.
If the current number is greater than expected, we found the gap.

Return expected.

Example Walkthrough

1Sort the array: [-1, 1, 3, 4]. Initialize expected = 1

-1

1/4

Code

Complexity Analysis

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 gets us to O(1) space but O(n log n) time. Instead of ordering every element, what if we just placed each relevant value (1 through n) directly at its "home" index?

Approach 3: Cyclic Sort (Optimal)

Intuition

Here's the key idea: we can use the input array itself as a hash map.

Since the answer is always in the range [1, n+1], we want to check which numbers from 1 to n are present. If we could place each value i at index i-1 (so value 1 goes to index 0, value 2 goes to index 1, and so on), then finding the answer becomes a simple scan: the first index where nums[i] != i + 1 tells us i + 1 is missing.

The technique is called cyclic sort. For each position, we repeatedly swap the current element to its correct position until either the current element is out of range (negative, zero, or greater than n), the current element is already in its correct position, or the target position already has the correct value (a duplicate).

After this rearrangement, one pass through the array gives us the answer.

Algorithm

For each index i from 0 to n-1:

While nums[i] is in range [1, n] and nums[i] is not in its correct position:

Swap nums[i] with nums[nums[i] - 1] (put it where it belongs).

Scan the array: return the first i + 1 where nums[i] != i + 1.
If all positions are correct, return n + 1.

Example Walkthrough

1Initialize: i=0, nums = [3, 4, -1, 1]

-1

1/8

Code

Why does this work?

The while loop might look like it could run forever, but each swap places at least one element in its correct final position. Since there are n positions and each element can be placed correctly at most once, the total number of swaps across the entire outer loop is at most n. So even though there's a while loop inside a for loop, the overall time is still O(n).

The condition nums[nums[i] - 1] != nums[i] serves two purposes: it stops swapping when the element is already in the right place, and it handles duplicates (if the target position already has the correct value, swapping would be pointless and could loop forever).

Complexity Analysis

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.

First Missing Positive

Understanding the Problem

Key Constraints:

Approach 1: Hash Set

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Sorting

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Cyclic Sort (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium