1. Understanding the Problem

You are given an unsorted integer array nums. Your task is to return the smallest missing positive integer.

For example, given nums = [3, 4, -1, 1], the smallest missing positive integer is 2. Given nums = [1, 2, 0], the smallest missing positive integer is 3.

The Core Constraints (The Hard-Level Threshold):

While this problem statement sounds simple, the constraints are what make it notorious in technical interviews:

• You must implement an algorithm that runs in O(N) time.
• Your solution must use O(1) auxiliary space.
• The input array can contain negative numbers, zeros, duplicates, and large values far exceeding array bounds.

2. The Naive Approaches and Their Flaws

To appreciate the optimal solution, let's examine why traditional approaches fail the interview benchmarks:

Approach A: Sorting

Sort the array in ascending order and find the first positive number gap. While intuitive, sorting takes O(N log N) time, violating the linear time constraint.

Approach B: Hash Set Lookups

Insert every number into a Hash Set, then iterate from 1 upwards until you find a number not present in the set. This achieves O(N) time, but storing elements in a set uses O(N) extra space, failing the O(1) space constraint.

3. The Optimal Approach: Index Placement / Cyclic Swap (O(1) Space)

Here is the key breakthrough insight: For an array of size N, the smallest missing positive integer must fall within the range [1, N + 1].

If the array contains all numbers from 1 to N perfectly (e.g., [1, 2, 3]), the answer is N + 1 (which is 4). Otherwise, the missing number is guaranteed to be some integer between 1 and N.

Since the valid candidates lie strictly between 1 and N, we can use the array itself as a zero-indexed hash table! We place every valid positive number x at its correct index, which is x - 1:

• The number 1 should be placed at index 0.
• The number 2 should be placed at index 1.
• The number x should be placed at index x - 1.

We traverse the array and repeatedly swap elements into their correct homes. Numbers that are negative, zero, or greater than N are simply ignored because they cannot be the answer.

4. The Logic Step-by-Step

1. Rearrange the Array (In-Place Bucket/Cyclic Sort):
   • Iterate through the array with index i from 0 to N - 1.
   • While nums[i] is positive (nums[i] > 0), within bounds (nums[i] <= N), and not already at its correct position (nums[i] != nums[nums[i] - 1]):
     • Swap nums[i] with the element at its target position, nums[nums[i] - 1].
2. Find the First Discrepancy:
   • Scan the array from index 0 to N - 1.
   • The first index i where nums[i] != i + 1 reveals that i + 1 is missing. Return i + 1.
3. Fallback:
   • If every index contains its correct number (nums[i] == i + 1 for all i), then all numbers from 1 to N are present. Return N + 1.

5. Complexity Analysis

• Time Complexity: O(N) — Although there is a nested while loop, every swap puts at least one number into its permanent correct position. An element is swapped at most once into its target slot, resulting in an amortized O(N) total runtime.
• Space Complexity: O(1) — We modify the input array in-place and only use a few loop indices and swap variables. Memory usage is strictly constant!

6. Code Implementations

Expand the sections below to see the optimal O(1) space index placement implementations across different languages.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        
        # Step 1: Place each positive number x at index x - 1
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # Swap nums[i] with target element at nums[nums[i] - 1]
                target_idx = nums[i] - 1
                nums[i], nums[target_idx] = nums[target_idx], nums[i]
                
        # Step 2: Find the first index missing its correct number
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
                
        # Step 3: If all numbers 1..n are present, answer is n + 1
        return n + 1

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // Step 1: Place each positive number x at index x - 1
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // Swap nums[i] with target element
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        
        // Step 2: Find the first index missing its correct number
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // Step 3: If all numbers 1..n are present, answer is n + 1
        return n + 1;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();
        
        // Step 1: Place each positive number x at index x - 1
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }
        
        // Step 2: Find the first index missing its correct number
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        // Step 3: If all numbers 1..n are present, answer is n + 1
        return n + 1;
    }
};

7. Conclusion: You Are Ready

Congratulations! You have just conquered a classic LeetCode Hard problem. The idea of turning an input array into its own implicit hash map by swapping elements into matching index locations is one of the most powerful paradigms in computer science. Whenever you encounter array problems with O(1) space constraints and bound limits on value ranges, think of this in-place index mapping trick. Keep pushing your limits, and happy coding!