LeetCode 41 - First Missing Positive

LeetCode Problem 41

Difficulty: 🔴 Hard
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to find the smallest positive integer that does not appear in an unsorted integer array.

The key detail is that we only care about positive integers starting from 1. Negative numbers, zero, and very large positive numbers are irrelevant unless they affect the placement of smaller positive integers.

For example:

• In [1,2,0], the numbers 1 and 2 exist, so the smallest missing positive is 3.
• In [3,4,-1,1], the number 1 exists but 2 does not, so the answer is 2.
• In [7,8,9,11,12], the number 1 itself is missing, so the answer is 1.

The constraints are extremely important:

• The array length can be as large as 10^5
• The solution must run in O(n) time
• The solution must use O(1) auxiliary space

These constraints immediately eliminate many straightforward approaches. For example, sorting would take O(n log n) time, which is too slow according to the strict requirement. Using a hash set would achieve O(n) time, but it would require O(n) extra space, which also violates the requirement.

An important observation is that for an array of length n, the answer must lie in the range [1, n + 1].

Why?

• If every number from 1 to n exists, then the answer is n + 1
• Otherwise, some number in [1, n] is missing

This means numbers less than or equal to 0, and numbers greater than n, can safely be ignored because they cannot affect the final answer.

Several edge cases are important:

• Arrays containing only negative numbers
• Arrays missing 1
• Arrays containing duplicates
• Arrays already containing all numbers from 1 to n
• Arrays containing very large irrelevant values

The challenge is to rearrange the array in-place so that each value is placed where it logically belongs.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly check whether 1 exists, then whether 2 exists, then 3, and so on.

For each candidate number, we scan the entire array looking for it. The first number not found is the answer.

This works because eventually we must encounter a missing positive integer.

However, the time complexity is too large. In the worst case, for an array of length n, we may scan the array n times, leading to O(n^2) complexity.

Another common brute-force improvement is to use a hash set:

• Insert every number into a set
• Start from 1
• Return the first number not found in the set

This achieves O(n) time, but requires O(n) extra space, which violates the problem constraints.

Key Insight for the Optimal Solution

The critical insight is that every positive integer x in the range [1, n] belongs at index x - 1.

For example:

• 1 should be at index 0
• 2 should be at index 1
• 3 should be at index 2

If we rearrange the array so that every valid number is placed into its correct position, then we can scan the array afterward:

• If nums[i] != i + 1, then i + 1 is missing
• If every position is correct, then the answer is n + 1

This technique works because the array itself acts like a hash map, allowing us to achieve constant auxiliary space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scan the array for each positive integer
Optimal	O(n)	O(1)	Place each number into its correct index position

Algorithm Walkthrough

Optimal In-Place Cyclic Placement Algorithm

1. Iterate through the array from left to right.

For each position i, examine the current value nums[i]. 2. Determine whether the current number belongs somewhere in the array.

A number is useful only if:

• It is positive
• It is less than or equal to n

Numbers outside this range cannot influence the smallest missing positive. 3. Compute the correct position for the current value.

If the current value is x, then its correct index is:

$\text{target index} = x - 1$ 4. Swap the current number into its correct position.

Suppose we are at index i and the value is x.

If:

• 1 <= x <= n
• nums[x - 1] != x

then swap:

nums[i] <-> nums[x - 1]

This places x into the position where it belongs. 5. Continue swapping until the current position is stable.

After a swap, the new value at nums[i] may also belong somewhere else. Therefore, we continue processing the same index until:

• The value is invalid
• The value is already in the correct position
• A duplicate would create an infinite swap loop

6. After the placement phase finishes, scan the array again.

At index i:

• If nums[i] != i + 1
• Then i + 1 is the smallest missing positive

7. If every position is correct, return n + 1.

This means all integers from 1 through n are present.

Why it works

The algorithm maintains the invariant that whenever possible, each valid number x is moved to index x - 1.

After the rearrangement phase:

• If a number k exists in the array, it will be placed at index k - 1
• Therefore, the first index where this property fails directly identifies the missing positive integer

Because each swap places at least one number into its final position, the total number of swaps across the entire algorithm is linear.

Python Solution

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        i = 0
        while i < n:
            current = nums[i]
            correct_index = current - 1

            if (
                1 <= current <= n
                and nums[correct_index] != current
            ):
                nums[i], nums[correct_index] = (
                    nums[correct_index],
                    nums[i],
                )
            else:
                i += 1

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

The implementation follows the exact algorithm described earlier.

First, we store the array length in n. This helps determine which values are relevant. Only numbers in the range [1, n] can possibly affect the answer.

The while loop performs the in-place placement process. Unlike a standard for loop, we do not always advance the index immediately because after a swap, the newly arrived value at the current index may also need to be repositioned.

For each value:

• We compute its intended location using current - 1
• We check whether the value is valid
• We ensure we are not swapping duplicates

If the value belongs elsewhere, we swap it into the correct position.

Once every valid number is positioned correctly, the second loop scans the array from left to right. The first location where nums[i] != i + 1 reveals the missing positive integer.

If no mismatch exists, then all numbers from 1 through n are present, so the answer must be n + 1.

Go Solution

func firstMissingPositive(nums []int) int {
	n := len(nums)

	i := 0
	for i < n {
		current := nums[i]
		correctIndex := current - 1

		if current >= 1 &&
			current <= n &&
			nums[correctIndex] != current {

			nums[i], nums[correctIndex] =
				nums[correctIndex], nums[i]
		} else {
			i++
		}
	}

	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}

	return n + 1
}

The Go implementation mirrors the Python logic very closely.

A few Go-specific details are worth noting:

• Go slices are reference-like structures, so modifications happen in-place automatically.
• There is no concern about integer overflow because all operations involve indices and comparisons within array bounds.
• The multiple assignment syntax in Go allows clean in-place swapping without temporary variables.
• Empty slices are handled naturally because the loops simply do not execute.

Worked Examples

Example 1

Input:

nums = [1,2,0]

Placement Phase

Step	Index	Array State	Action
Start	-	[1,2,0]	Initial array
1	0	[1,2,0]	1 already in correct position
2	1	[1,2,0]	2 already in correct position
3	2	[1,2,0]	0 ignored because not positive

Scan Phase

Index	Expected	Actual	Result
0	1	1	Correct
1	2	2	Correct
2	3	0	Missing number found

Answer:

3

Example 2

Input:

nums = [3,4,-1,1]

Placement Phase

Step	Index	Array State	Action
Start	-	[3,4,-1,1]	Initial array
1	0	[-1,4,3,1]	Swap 3 into index 2
2	0	[-1,4,3,1]	-1 ignored
3	1	[-1,1,3,4]	Swap 4 into index 3
4	1	[1,-1,3,4]	Swap 1 into index 0
5	1	[1,-1,3,4]	-1 ignored
6	2	[1,-1,3,4]	3 already correct
7	3	[1,-1,3,4]	4 already correct

Scan Phase

Index	Expected	Actual	Result
0	1	1	Correct
1	2	-1	Missing number found

Answer:

2

Example 3

Input:

nums = [7,8,9,11,12]

Placement Phase

All values are larger than n = 5, so every value is ignored.

Step	Index	Array State	Action
Start	-	[7,8,9,11,12]	Initial array
1	0	[7,8,9,11,12]	Ignore 7
2	1	[7,8,9,11,12]	Ignore 8
3	2	[7,8,9,11,12]	Ignore 9
4	3	[7,8,9,11,12]	Ignore 11
5	4	[7,8,9,11,12]	Ignore 12

Scan Phase

Index	Expected	Actual	Result
0	1	7	Missing number found

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number is moved at most once into its correct position
Space	O(1)	Rearrangement happens entirely in-place

Although the algorithm contains nested behavior through repeated swaps, each swap places at least one number into its final position. Therefore, the total number of swaps across the whole execution is bounded by n, giving linear overall time complexity.

No auxiliary data structures proportional to input size are used, so the extra space remains constant.

Test Cases

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)

        i = 0
        while i < n:
            current = nums[i]
            correct_index = current - 1

            if (
                1 <= current <= n
                and nums[correct_index] != current
            ):
                nums[i], nums[correct_index] = (
                    nums[correct_index],
                    nums[i],
                )
            else:
                i += 1

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

solution = Solution()

assert solution.firstMissingPositive([1, 2, 0]) == 3
# Missing number after consecutive positives

assert solution.firstMissingPositive([3, 4, -1, 1]) == 2
# Mixed positive and negative numbers

assert solution.firstMissingPositive([7, 8, 9, 11, 12]) == 1
# Missing 1 entirely

assert solution.firstMissingPositive([1, 2, 3]) == 4
# All consecutive positives present

assert solution.firstMissingPositive([2]) == 1
# Single element missing 1

assert solution.firstMissingPositive([1]) == 2
# Single element containing 1

assert solution.firstMissingPositive([-1, -2, -3]) == 1
# All negatives

assert solution.firstMissingPositive([0, 0, 0]) == 1
# All zeros

assert solution.firstMissingPositive([1, 1]) == 2
# Duplicate values

assert solution.firstMissingPositive([2, 2, 2]) == 1
# Duplicates without 1

assert solution.firstMissingPositive([4, 3, 2, 1]) == 5
# Reverse ordered valid range

assert solution.firstMissingPositive([1, 1000]) == 2
# Large irrelevant value

assert solution.firstMissingPositive([3, 1, 2]) == 4
# Values requiring multiple swaps

assert solution.firstMissingPositive([2, 1]) == 3
# Two elements already cover range

assert solution.firstMissingPositive([5, 4, 3, 2, 1]) == 6
# Complete range in reverse order

Test	Why
[1,2,0]	Basic example with zero
[3,4,-1,1]	Mixed valid and invalid values
[7,8,9,11,12]	No useful values present
[1,2,3]	Entire range exists
[2]	Smallest possible missing value
[1]	Single valid element
[-1,-2,-3]	All negatives
[0,0,0]	All zeros
[1,1]	Duplicate valid values
[2,2,2]	Duplicate invalid range coverage
[4,3,2,1]	Reverse ordering
[1,1000]	Large irrelevant positive
[3,1,2]	Multiple swaps required
[2,1]	Small complete range
[5,4,3,2,1]	Reverse complete range

Edge Cases

One important edge case is when the array does not contain 1.

For example:

[2,3,4]

The smallest missing positive must immediately be 1. A naive implementation that only looks for gaps between existing numbers may incorrectly return another value. The algorithm handles this naturally because index 0 is expected to contain 1. During the final scan, the mismatch is detected immediately.

Another critical edge case involves duplicate values.

For example:

[1,1]

Without careful duplicate handling, the swapping process could enter an infinite loop because both positions contain the same value. The condition:

nums[correct_index] != current

prevents unnecessary swaps and guarantees progress.

A third important edge case occurs when values are outside the useful range.

For example:

[-10, 100, 200]

These numbers cannot affect the smallest missing positive because for an array of length n, only numbers in [1, n] matter. The implementation safely ignores such values during the placement phase.

Another subtle case is when the array already contains every number from 1 through n.

For example:

[1,2,3,4]

In this situation, the answer is not within the array range, it is n + 1. The final return statement correctly handles this scenario after the scan finds no mismatches.