💬 Discord
Sign In
NeetCode #171LC-41HardArrays & HashingNC 250
← Back to All Problems

#171 · #41 · First Missing Positive(缺失的第一个正数)

📌 Problem Statement & Constraints

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums. Constraints: 1 <= nums.length <= 10^5, -2^31 <= nums[i] <= 2^31 - 1. You must run in O(n) time and use O(1) auxiliary space.

💡 Core Algorithmic Approaches

  1. The answer is always in the range [1, n + 1], because a permutation of 1..n would make the answer n + 1. This bounds the problem usefully.
  2. Cyclic sort / index placement: repeatedly swap so that the value v ends up at index v - 1, whenever 1 <= v <= n.
  3. Use a while loop for the swap so that each value keeps moving until it reaches its home. Each successful placement fixes one element permanently, so the total work is O(n).
  4. After the rearrangement, scan for the first index i where nums[i] != i + 1. That index gives the answer i + 1; if none is found, the answer is n + 1.

💻 Benchmark Python3 Implementation

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # keep swapping nums[i] to its home index (nums[i] - 1)
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                target = nums[i] - 1
                nums[i], nums[target] = nums[target], nums[i]
        # the first slot not holding i+1 reveals the answer
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) amortised. The nested while looks quadratic, but every swap places one value at its final home and that value never moves again, so there are at most n swaps in total.
💾 Space Complexity
O(1) auxiliary: the rearrangement happens inside nums. A hash-set solution would be O(n) space, which the constraints forbid.

⚠️ Interview Pitfalls & Follow-ups

  • Using a set: O(n) time but O(n) space, violating the O(1) requirement. It is the correct baseline to mention before improving.
  • Forgetting the upper bound nums[i] <= n: values larger than n (or non-positive) have no home index and must be left alone, otherwise you index out of range.
  • Using the condition nums[i] != i + 1 instead of nums[nums[i]-1] != nums[i]: the correct guard detects when the destination already holds the right value, which is what prevents an infinite swap loop on duplicates.
  • Using an if instead of while: a single pass would leave some values unmoved; the while keeps pushing until the value settles.
  • Assuming the array must contain all of 1..n: it need not, which is exactly why the final scan exists.