LC 41. First Missing Integer (Hard)

Problem Statement

Given an unsorted integer array A, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1

Input:

A = [1, 0, 2]

Output:

3

Explanation:

The numbers in the range [1,2] are all in the array.

Example 2

Input:

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

Output:

2

Explanation:

1 is present in the array but 2 is missing. Also, we need the first missing positive integer, so 0 and negative numbers do not matter.

This was the question I did today in my morning session.

Looking at the problem, if no time complexity or space complexity constraint was given, I thought of the brute force approach first. My idea was that I could sort the array and then use a loop.

Starting with:

int expected = 1;

I can check every number in the sorted array.

• Ignore negatives.

• Ignore duplicates.

• If the current number is equal to expected, increment expected.

• If the current number becomes greater than expected, then expected is the smallest missing positive number.

I got this approach because I have solved a medium-level question on missing and repeated numbers before.

The brute force code would look something like:

int expected = 1;

for(int num : arr) {

    if(num < expected)
        continue;

    if(num == expected)
        expected++;

    else if(num > expected)
        return expected;
}

return expected;

This approach works, but sorting itself takes:

O(n log n)

and the question specifically asks for:

O(n)

So I had to think:

How can I sort without actually using a sorting function?

And thatttt really opened my brain.

I spent around 30 minutes thinking about it, and when I couldn't get there, I used ChatGPT as a mentor to help me understand how someone would arrive at that approach.

Let's take this example:

[3,4,-1,1]

If I think about the positive numbers only, then for an array of length 4, the numbers that actually matter are:

1, 2, 3, 4

A very important observation here is that the answer will always lie between:

1 and n+1

where n is the length of the array.

So for this example:

n = 4

The answer must lie between:

1 and 5

That means:

• Negative numbers do not matter.

• 0 does not matter.

• Numbers greater than n do not matter.

Now imagine the array was already perfectly sorted.

It would look like:

1 -> index 0
2 -> index 1
3 -> index 2
4 -> index 3

Notice the pattern:

index = value - 1

or

value = index + 1

This observation is the entire foundation of the solution.

Now to the sorting part.

We cannot use a sorting function.

So can we somehow sort it ourselves?

What if we directly put every number at its correct index?

Let's go back to the example:

[3,4,-1,1]

Here:

3

is present at:

index = 0

but its correct position should be:

index = 2

because:

3 -> index 2

So we swap it.

[-1,4,3,1]

Now:

4

is present at:

index = 1

Its correct position should be:

index = 3

Swap again.

[1,-1,3,4]

Now check the positions:

index 0 -> 1 ✓
index 1 -> should contain 2 ✗

So the first missing positive number is:

2

Another example:

[7,8,9,11,12]

n = 5

Notice that every number is greater than n.

Since none of them belong to the valid range:

1 to n

no swapping is required.

Now check the positions.

At:

index 0

we should have:

1

but we don't.

So the smallest missing positive number is:

1

and not 5.

This was an edge case that helped me understand why numbers greater than n are irrelevant.

Another thing that confused me initially was:

Why are we using a while loop and not a for loop?

Suppose:

[2,3,1]

At index 0:

2

belongs to:

index 1

After swapping:

[3,2,1]

Now a new number has arrived at index 0.

That new number also needs to be checked.

So after a swap, we stay at the same index and keep fixing it until:

• The number is at the correct place.

• The number is invalid.

• The number is a duplicate.

Only then do we move forward.

That is why a while loop feels more natural here.

The important things I noticed were:

1. Only numbers in the range:

1 to n

matter.

1. Negative numbers, 0, and numbers greater than n can be ignored.

2. Every value wants to sit at:

value - 1

1. If the number is already at its correct place, we do not swap it.

2. If the correct position already contains the same value, we do not swap it again, otherwise we can get stuck in an infinite loop.

3. After placing all valid numbers at their correct positions, the first index where:

A[i] != i + 1

gives us the answer.

1. If all positions are correct, then the answer is:

n + 1

because all numbers from:

1 to n

already exist.

This is the code that I wrote (ss and code both btw ):

public class Solution {

    public int firstMissingPositive(int[] A) {

        int n = A.length;
        int i = 0;

        while(i < n) {

            int correctIdx = A[i] - 1;

            if(A[i] >= 1 &&
               A[i] <= n &&
               A[i] != A[correctIdx]) {

                int temp = A[i];
                A[i] = A[correctIdx];
                A[correctIdx] = temp;
            }
            else {
                i++;
            }
        }

        for(i = 0; i < n; i++) {

            if(A[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

My biggest learning from this question was that sometimes the goal is not to sort the array using a sorting algorithm. Sometimes the goal is to think:

Can I place elements directly where they belong and get the effect of sorting without actually sorting?

Woww, this was my first DSA article 😭It took me way more time than I expected because explaining my thinking was honestly harder than writing the code itself lol.

I'll try to continue this series and document more problems as I learn.
Any suggestions, corrections, or feedback would be appreciated.

Thanks for reading!!