Introduction

Finding the smallest positive integer missing from an unsorted array appears simple at first, but the problem becomes significantly more interesting because of its strict constraints.

Problem Link -: First Missing Positive

Given an unsorted integer array nums, the task is to return the smallest positive integer that does not appear in the array.

For example:

The positive integers begin with:

Both 1 and 2 are present, while 3 is missing.

Therefore, the answer is:

The challenge is that the solution must run in:

This rules out several common approaches such as sorting and using a HashSet.

Problem Statement

Given an unsorted integer array nums, return the smallest positive integer that is not present in the array.

Example

The positive integers are:

1 exists in the array, but 2 does not.

Therefore:

Another example:

Since 1 itself is missing, the answer is immediately:

Understanding the Important Observation

For an array of length n, the answer can never be greater than:

Consider:

The first three positive integers are present:

Therefore, the smallest missing positive integer is:

Since n = 3:

This observation is the key to the optimal solution.

Numbers that are:

or

cannot directly determine the smallest missing positive number.

The useful values are only:

The Submitted HashSet Approach

A straightforward approach is to store every value in a HashSet and then search for the first missing positive integer.

The basic idea is:

The submitted implementation follows this idea:

This approach is logically valid for finding the answer, but it does not satisfy the required constraints.

Space Complexity

The HashSet can store up to n elements.

Therefore:

The problem requires:

So a different technique is required.

Why Sorting Is Also Not Enough

Sorting the array might appear to solve the problem easily.

For example:

After sorting:

The missing positive integer can then be identified by scanning the array.

However, sorting requires:

time in the general case.

The problem specifically requires:

time.

Therefore, sorting does not satisfy the required complexity either.

The Core Idea: Put Every Number in Its Correct Position

The optimal solution uses an in-place cyclic placement technique.

The important relationship is:

In general:

Consider:

The desired arrangement for useful values is:

After placing the valid values into their corresponding positions, the array can become:

Index 1 should contain:

but it contains -1.

Therefore:

This transforms the problem from:

Search for a missing number.

into:

Place every useful number at the position where it belongs, then find the first incorrect position.

Which Numbers Should Be Placed?

For an array of length n, only values satisfying:

need to be placed.

Why?

Suppose:

The answer can only be one of:

A value such as:

cannot be the answer.

Similarly:

cannot prevent 1...6 from determining the answer.

Therefore, values outside the range [1,n] can safely remain where they are.

The Cyclic Placement Process

For every index i, check the current value:

If it belongs to the range:

its correct index is:

So the value should be swapped into:

The process continues until the current position contains a value that either:

1. is outside the useful range, or
2. is already in its correct position.

Why the Duplicate Check Is Necessary

Consider:

The value 1 belongs at index 0.

The first element is already correct.

At index 1, the value is again 1.

Trying to swap it repeatedly would cause an infinite loop because another 1 already occupies its correct position.

Therefore, the swap condition must also ensure:

This duplicate check is extremely important.

Optimized Java Solution

Dry Run

Consider:

Array length:

Initial Array

At index 0:

The correct index for 3 is:

Swap:

The value at index 0 is now -1.

Since -1 is outside [1,4], no further placement is required for this index.

At index 1:

Correct index:

Swap:

Now:

The correct index of 1 is 0.

Swap:

Now index 1 contains -1, so placement stops.

Final Arrangement

The expected value at each index is:

The first incorrect position is:

Therefore:

Another Example

Consider:

The values 1 and 2 are already in their correct positions:

Expected arrangement:

The first incorrect position is index 2.

Therefore:

Edge Case: All Positive Numbers Are Present

Consider:

Every position contains the expected value:

No missing value exists between 1 and n.

Therefore, the smallest missing positive integer is:

So:

Edge Case: The Answer Is 1

Consider:

All values are greater than 1.

After the placement phase, there is no 1 at index 0.

Therefore:

Complexity Analysis

The algorithm uses the array itself to store values in their correct positions.

Time Complexity

Although the algorithm contains a nested while loop, the total number of swaps is bounded by O(n) because every successful swap places a useful value into its correct position.

Therefore:

Space Complexity

No additional data structure proportional to the input size is used.

Only a few variables are required:

This satisfies the required constraints.

Why the Algorithm Works

The central invariant is:

Whenever a value x lies in the range [1,n], the algorithm attempts to place it at index x-1.

After the placement phase, every value that can occupy a meaningful position is either:

or

Therefore, scanning from left to right provides a direct answer.

If:

then i + 1 is missing.

If every position is correct, then all values from:

exist, making:

the smallest missing positive integer.

Interview Insight

This problem is an important example of in-place array positioning.

The key pattern is:

Whenever an array problem asks for a missing, duplicate, or misplaced number within a known range, it is worth checking whether the values themselves can be mapped directly to indices.

This technique appears in several interview problems involving:

1. Missing numbers
2. Duplicate numbers
3. Cyclic sort
4. In-place rearrangement
5. Frequency representation without extra memory

The biggest clue in this problem is the combination of:

That combination strongly suggests an in-place index/value mapping strategy.

Conclusion

LeetCode 41, First Missing Positive, is a classic example of turning the array itself into auxiliary storage.

A HashSet provides an easy solution but requires O(n) extra space. Sorting simplifies the search but requires O(n log n) time. The optimal solution instead uses the relationship:

to rearrange useful values directly inside the input array.

After this placement, the first index whose value does not match index + 1 identifies the smallest missing positive integer.

The final complexity is:

making the approach suitable for the strict constraints and an important pattern to recognize in technical interviews.