[/dsa/leetcode]

41 - First Missing Positive

Wednesday, 16 September 2026

<hard> [problem]

Cyclic sort with a range guard, so junk outside [1, n] is left where it lies and the first slot not holding its own value is the answer.

{array}{hashing}

Problem

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums.

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

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

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

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

Constraints:

  • 1 <= nums.length <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

Approach

The answer is always in [1, n + 1]. n slots can hold at most n distinct positive integers, so the n + 1 candidates 1, 2, ..., n + 1 cannot all be present - one of them must be missing. That means every value outside [1, n] is irrelevant. Negatives, zeros, 10^9, INT_MIN - none of them can be the answer and none of them can stop a value in [1, n] from being the answer. They are noise occupying space.

So it is the same problem after all: place each value v in [1, n] at index v - 1, and the first slot that doesn’t hold its own value names the answer.

Cyclic Sort with a Range Guard

The only addition over the earlier problems is the guard. nums[corr - 1] is a legal index only when corr is in [1, n], so out-of-range values are skipped rather than placed — i++ moves past them and they stay wherever they happened to be.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int i = 1;
        int n = nums.size();
        while (i <= n) {
            int corr = nums[i - 1];
            if (corr <= n && corr > 0 && nums[corr - 1] != corr) {
                swap(nums[corr - 1], nums[i - 1]);
            } else {
                i++;
            }
        }
        for (int j = 1; j <= n; j++)
            if (nums[j - 1] != j)
                return j;
        return n + 1;
    }
};
nums = [3, 4, -1, 1]
i=1  corr=3   in range, nums[2]=-1 != 3, swap   -> [-1, 4, 3, 1]
i=1  corr=-1  out of range                      -> i=2
i=2  corr=4   in range, nums[3]=1 != 4, swap    -> [-1, 1, 3, 4]
i=2  corr=1   in range, nums[0]=-1 != 1, swap   -> [1, -1, 3, 4]
i=2  corr=-1  out of range                      -> i=3
i=3  corr=3   nums[2]=3 == 3                    -> i=4
i=4  corr=4   nums[3]=4 == 4                    -> i=5, stop

scan: slot 1 holds 1, slot 2 holds -1 != 2  ->  return 2
  • time: O(n) — every swap puts one value permanently home, so at most n swaps across the whole loop, plus at most n increments of i
  • space: O(1) — in place, which is what makes this a hard problem rather than a trivial one
quantinium © 2026