Find the Smallest Missing Positive Integer in O(n) Time and O(1) Space

Problem Description

Problem: Given an unsorted integer array, return the smallest positive integer that does not appear in the array. Constraints: Time complexity O(n), space complexity O(1). Example 1: Input: nums = [3, 1, 2, 4] Output: 5 Example 2: Input: nums = [-3, 1, 0, 4] Output: 2 Example 3: Input: nums = [6, 8, 7, 8] Output: 1

Please think about the problem before reading the solution.

Problem Analysis

Step 1: Ordered Array

If we only needed the smallest positive integer that exists, a single pass with a variable would suffice. However, we need the smallest missing positive integer, which requires arranging the array in a certain order. If the array were sorted, a single pass would be enough.

Typical sorting algorithms like quicksort or mergesort are O(n log n) and exceed the time limit. Counting sort runs in O(n) time but its space depends on the value range, which can be billions, violating the O(1) space constraint.

Step 2: Core Insight

The range of the missing smallest positive integer is limited to [1, n+1] where n is the length of the array.

If the array contains [1, 2, 3, ..., n], the answer is n+1.

Otherwise, the answer lies within [1, n].

Thus we can place each element whose value falls in [1, n] into its “correct” position (value v should be at index v‑1) using only the original array.

Step 3: Implementation Details

Iterate over the array and for each index i handle three cases:

The element cannot be placed (value ≤0, >n, or already in correct position). Just move to the next index.

The element’s target position already holds the same value (duplicate). Skip it.

The element itself is already a correctly placed element.

The element is a non‑placeable element.

Other cases: swap the current element with the element at its target position and re‑evaluate the new element at index i.

After swapping, continue processing the new element at the same index.

After the first pass, perform a second pass to find the first index i where nums[i] != i+1. That i+1 is the missing integer; if none is found, the answer is n+1.

Implementation Code

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[i] != nums[nums[i]-1]:
            nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
    for i in range(n):
        if nums[i] != i+1:
            return i+1
    return n+1

Complexity Analysis

Time Complexity: Each element is swapped at most once, so the overall time is O(n).

Space Complexity: The algorithm operates in‑place, using O(1) extra space.

Conclusion

The key is to reorder the array so that each value v (if 1 ≤ v ≤ n) occupies index v‑1; then the first mismatch reveals the smallest missing positive integer.