First Missing Positive Solution

Problem

Given an unsorted array of integers, find the smallest positive integer that does not appear in it. Your solution must run in O(n) time and use O(1) extra space — meaning you cannot allocate a separate hash table.

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: 1 is present, but 2 is missing.

Counter-example: nums = [7, 8, 9, 11, 12] → output 1, because 1 is entirely absent even though several large numbers exist.

Intuition

The answer must fall in the range [1, n+1] where n is the array length — at most n positive integers can fit in n slots, so if all of 1 through n are present the answer is n+1. This bound means we can use the array itself as our hash map: value x (if it's in [1, n]) belongs at index x-1. After rearranging the array so each valid value sits at its correct index, the first index i where nums[i] != i+1 reveals the answer.

Approach 1 — Hash Set

Scan the array once into a set, then probe 1, 2, 3... until a miss is found. Straightforward but allocates O(n) extra memory.

Add every integer from nums into a hash set.
Starting from 1, check each candidate integer against the set.
Return the first candidate not in the set.

1def firstMissingPositive(nums):
2    seen = set(nums)
3    candidate = 1
4    while candidate in seen:
5        candidate += 1
6    return candidate

Time: O(n) — one pass to build the set, then at most n+1 probes.
Space: O(n) — the hash set stores up to n elements.

Approach 2 — Cyclic Sort (In-Place)

Reuse the input array as the hash map. For each position, repeatedly swap the current value to its correct index until the slot holds the right value or an out-of-range value. A second scan then finds the first mismatch.

For each index i, while nums[i] is in [1, n] and isn't already sitting at the correct index, swap it to index nums[i] - 1.
Check nums[nums[i] - 1] != nums[i] before swapping to avoid infinite loops on duplicates.
After all swaps, scan from left to right.
Return the first i + 1 where nums[i] != i + 1.
If every position is correct, return n + 1.

1def firstMissingPositive(nums):
2    n = len(nums)
3
4    for i in range(n):
5        # Swap nums[i] to its home index until it's in the right place or out of range
6        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
7            correct_idx = nums[i] - 1
8            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
9
10    for i in range(n):
11        if nums[i] != i + 1:
12            return i + 1
13
14    return n + 1

Time: O(n) — each element is moved to its correct position at most once; the outer loop visits each index once, so total swaps across all iterations is bounded by n.
Space: O(1) — all rearranging is done in place with no auxiliary structures.

Complexity Summary

Approach	Time	Space	When to use
Hash Set	O(n)	O(n)	When code clarity matters more than memory, or if modifying the input is forbidden
Cyclic Sort	O(n)	O(1)	When you must respect the O(1) space constraint in interviews or embedded contexts

Common Mistakes

Infinite loop on duplicates — without the guard nums[nums[i] - 1] != nums[i], an array like [1, 1] causes endless swapping between the same two indices. The guard short-circuits once the destination already has the correct value.
Swapping to the wrong index — value x belongs at index x - 1, not index x. Getting this backwards places every element one slot too far to the right, corrupting the entire scan.
Not capturing the target index before swapping (C++) — swap(nums[i], nums[nums[i]-1]) has undefined evaluation order in C++; the index must be saved in a local variable first.
Skipping the n + 1 return — if the input is [1, 2, 3], every position is filled correctly and the loop finds no mismatch. Omitting return n + 1 at the end produces a wrong or missing answer.
Checking only nums[i] > 0 — values larger than n are harmless and need no placement; placing them would write out of bounds. The upper bound nums[i] <= n is essential, not optional.

First Missing Positive — Solution