Amazon Interview | LeetCode 41 | First Missing Positive Explained: An O(n) In-Place Solution (Python)

devscall.com

Some interview problems look deceptively easy until you read the constraints. LeetCode 41 — First Missing Positive is one of them. Finding the smallest missing positive integer sounds straightforward, but the requirement to solve it in O(n) time using O(1) extra space rules out many common approaches. The key lies in recognizing that the array itself can be rearranged to act like a lookup table, leading to an elegant in-place solution.

• Time Complexity: O(n)
• Extra Space: O(1)

These constraints eliminate the possibility of using sorting or additional data structures like sets or hash maps.

Let’s understand the intuition behind the optimal solution step by step.

Problem Statement

Given an unsorted integer array nums, return the first missing positive integer.

Example 1

Input: nums = [1,2,0]
Output: 3

Explanation:

Positive numbers present:
1 ✔
2 ✔

missing positive = 3

Example 2

Input: nums = [3,4,-1,1]
Output: 2

Explanation:

Positive numbers present:
1 ✔
3 ✔
4 ✔
missing positive = 2

Example 3

Input: nums = [7,8,9,11,12]
Output: 1

Explanation:

The smallest positive integer 1 is not present in the array.

Why the Obvious Approaches Don’t Work

Approach 1: Sorting

Sort the array and scan for the missing number.

Time Complexity = O(n log n)

Fails the O(n) requirement.

Approach 2: HashSet

Store all positive numbers in a set.

Time Complexity = O(n) , Space Complexity = O(n)

Fails the O(1) space requirement.

Key Observation

Suppose the array length is n.

The smallest missing positive can only be in the range:

1 ... n+1

For example,

n = 5
Possible answers:
1
2
3
4
5
6

Any number less than or equal to 0 is useless.

Any number greater than n is also irrelevant because it cannot affect the smallest missing positive within this range.

So we only care about numbers from 1 to n.

The Main Idea

Imagine every number has its own “home.”

Number 1 belongs at index 0
Number 2 belongs at index 1
Number 3 belongs at index 2
...
Number n belongs at index n-1

So,

Correct Index = Value - 1

Our goal is to place every valid number in its correct position.

Algorithm

Step 1

Traverse the array.

For every element,

correctPos = nums[i] - 1

If number is between 1 and n

• and it is not already in its correct position,swap it.

Continue swapping until the current index contains the correct number, an invalid number, or a duplicate.

Step 2

Traverse the array again.

The first index where

nums[i] != i + 1

gives the answer.

If every position is correct,

return

n + 1

Dry Run

Example

nums = [3,4,-1,1]
Initially,
Index : 0 1 2 3
Value : 3 4 -1 1

i = 0

Current value = 3

Get Pooja G’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Correct position = 2

Swap

[3,4,-1,1]
↓
[-1,4,3,1]

Current value becomes -1.

Since it’s invalid, stop.

i = 1

Current value = 4

Correct position = 3

Swap

[-1,4,3,1]
↓
[-1,1,3,4]
Current value becomes 1.
Correct position = 0
Swap again

[-1,1,3,4]
↓
[1,-1,3,4]

Current value becomes -1.
Stop.

i = 2

3 is already in its correct position.

i = 3

4 is already in its correct position.

Final array

[1,-1,3,4]

Now scan again.

Index 0
Expected 1
Found 1

Correct.

Index 1
Expected 2
Found -1

Mismatch.

Therefore,

Answer = 2

Why Do We Use a While Loop Instead of If?

Consider

nums = [2,3,1]
At index 0,
Current array
[2,3,1]

Swap 2.
↓
[3,2,1]

Now the current value becomes 3.

It is still not in its correct position.

Swap again.

↓
[1,2,3]

One swap wasn’t enough.

That’s why we continue swapping using a while loop until the current element reaches its correct position.

Understanding the While Condition

while 1 <= nums[i] <= n and nums[i] != nums[correctPos]:
Condition 1
1 <= nums[i] <= n

Ignore

• negative numbers
• zero
• numbers greater than n

because they can never occupy a valid position.

Condition 2

nums[i] != nums[correctPos]

This prevents infinite swapping in case of duplicates.

Example:

[1,1]

Without this check, we’d keep swapping 1 with 1 forever.

Python Solution

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            correctPos = nums[i] - 1
            while (
                1 <= nums[i] <= n
                and nums[i] != nums[correctPos]
            ):
                nums[i], nums[correctPos] = nums[correctPos],nums[i]
                correctPos = nums[i] - 1
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Complexity Analysis

Time Complexity

O(n)

Although there is a while loop inside a for loop, every element is moved to its correct position at most once. Therefore, the total number of swaps across the entire array is bounded by n.

Space Complexity

O(1)

The algorithm rearranges the input array in-place without using any extra data structures.

Key Takeaways

• The answer is always between 1 and n+1.
• Every value x ideally belongs at index x - 1.
• Ignore numbers less than or equal to 0 and greater than n.
• Use cyclic placement (in-place swapping) to position valid numbers correctly.
• Scan the array once more to find the first mismatch.
• This elegant approach satisfies both interview constraints: O(n) time and O(1) extra space.

Final Thoughts

This problem is a classic example of using the input array itself as a hash map by placing each number at its “correct” index. The idea may seem unusual at first, but once you understand the relationship between a value and its index, the solution becomes intuitive. This pattern — often called Cyclic Sort or Index Placement — appears in several coding interviews and is worth mastering.