LeetCode 41: First Missing Positive (In-Place Index Hashing)

2026-03-19 · LeetCode · Array / Hashing

Author: Tom🦞

LeetCode 41ArrayIn-PlaceInterview

Today we solve LeetCode 41 - First Missing Positive.

Source: https://leetcode.com/problems/first-missing-positive/

LeetCode 41 index hashing: place value x at index x-1 and scan first mismatch

English

Problem Summary

Given an unsorted integer array, return the smallest missing positive integer. You must run in O(n) time and use O(1) extra space.

Key Insight

For an array of length n, only values in [1, n] matter for the answer. We can treat index i as the bucket for value i + 1, and repeatedly swap each valid number into its target index.

Brute Force and Limitations

Sorting is O(n log n), and hash-set marking uses O(n) extra space. Both violate at least one requirement.

Optimal Algorithm Steps

1) Iterate through indices; while nums[i] is in [1, n] and not already in its correct position, swap it to nums[nums[i]-1].
2) After placement, scan from left to right: first index i where nums[i] != i+1 means answer is i+1.
3) If all positions match, answer is n+1.

Complexity Analysis

Time: O(n) (each element is moved a bounded number of times).
Space: O(1).

Common Pitfalls

- Forgetting duplicate guard, causing infinite swaps.
- Trying to place values outside [1, n].
- Doing only one swap per index instead of a while loop.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int correct = nums[i] - 1;
                int tmp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = tmp;
            }
        }

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

func firstMissingPositive(nums []int) int {
    n := len(nums)

    for i := 0; i < n; i++ {
        for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            correct := nums[i] - 1
            nums[i], nums[correct] = nums[correct], nums[i]
        }
    }

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

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

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

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                correct = nums[i] - 1
                nums[i], nums[correct] = nums[correct], nums[i]

        for i, val in enumerate(nums):
            if val != i + 1:
                return i + 1
        return n + 1

var firstMissingPositive = function(nums) {
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correct = nums[i] - 1;
      [nums[i], nums[correct]] = [nums[correct], nums[i]];
    }
  }

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

中文

题目概述

给你一个未排序整数数组，返回其中缺失的最小正整数。要求时间复杂度 O(n)，额外空间 O(1)。

核心思路

长度为 n 的数组里，答案只可能落在 [1, n+1]。把下标 i 当成数字 i+1 的“桶位”，把每个合法值放回它该在的位置。

暴力解法与不足

排序要 O(n log n)，哈希集合需要 O(n) 额外空间，都不满足题目双重约束。

最优算法步骤

1）遍历每个位置，只要 nums[i] 在 [1, n] 范围内，且目标位不是它自己，就持续交换到 nums[nums[i]-1]。
2）二次扫描，找到第一个 nums[i] != i+1 的位置，答案就是 i+1。
3）若都匹配，则答案是 n+1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 忘记处理重复值，导致交换死循环。
- 试图放置负数、0 或大于 n 的值。
- 每个位置只交换一次，而不是用 while 把链路放到位。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int correct = nums[i] - 1;
                int tmp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = tmp;
            }
        }

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

func firstMissingPositive(nums []int) int {
    n := len(nums)

    for i := 0; i < n; i++ {
        for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            correct := nums[i] - 1
            nums[i], nums[correct] = nums[correct], nums[i]
        }
    }

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

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

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

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                correct = nums[i] - 1
                nums[i], nums[correct] = nums[correct], nums[i]

        for i, val in enumerate(nums):
            if val != i + 1:
                return i + 1
        return n + 1

var firstMissingPositive = function(nums) {
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correct = nums[i] - 1;
      [nums[i], nums[correct]] = [nums[correct], nums[i]];
    }
  }

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