First Missing Positive

How it works

Another way to use the array as its own hash map is through cycle sort. The goal is to place each number at its "correct" index: value 1 at index 0, value 2 at index 1, and so on.

We iterate through the array, and for each element, if it's a valid positive number in range [1, n] and not already in its correct position, we swap it to where it belongs. We keep swapping until the current position holds the right value or an out-of-range number.

After this rearrangement, we scan the array. The first position where nums[i] != i + 1 gives us the missing number.

Steps

1. Iterate through the array with index i:
   • While nums[i] is in range [1, n] and nums[i] != nums[nums[i] - 1]:
     • Swap nums[i] with nums[nums[i] - 1].
2. Scan the array:
   • Return i + 1 for the first index where nums[i] != i + 1.
3. If all positions are correct, return n + 1.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting the Answer is Bounded by n+1

The first missing positive is always in the range [1, n+1]. Many solutions fail by not recognizing this constraint and trying to handle arbitrarily large numbers. If the array contains [1, 2, ..., n], the answer is n+1. This insight is crucial for achieving O(n) time and O(1) space.

Not Handling Negative Numbers and Zeros

The array can contain negative numbers, zeros, and duplicates. Solutions that use the array itself as a hash map (via negative marking or cycle sort) must first handle or ignore non-positive values. Forgetting to skip or neutralize these values leads to index-out-of-bounds errors or incorrect markings.

Infinite Loops in Cycle Sort

When using cycle sort, failing to check if nums[i] != nums[nums[i] - 1] before swapping causes infinite loops. If the current element equals the element at its target position (duplicate case), you must move forward instead of swapping. Always verify both the value is in range and the target position needs updating.

Corrupting Original Values Before Using Them

In negative marking approaches, reading nums[i] after it has been negated gives the wrong value. Always use abs(nums[i]) to retrieve the original value when the array has been modified. Similarly, marking a zero requires special handling since negating zero has no effect.

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] <= 0 or nums[i] > n:
                i += 1
                continue

            index = nums[i] - 1
            if nums[i] != nums[index]:
                nums[i], nums[index] = nums[index], nums[i]
            else:
                i += 1

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int i = 0;

        while (i < n) {
            if (nums[i] <= 0 || nums[i] > n) {
                i++;
                continue;
            }
            int index = nums[i] - 1;
            if (nums[i] != nums[index]) {
                swap(nums[i], nums[index]);
            } else {
                i++;
            }
        }

        for (i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};