LeetCode Hot 100 P41 First Missing Positive

---

Timeline

timeline

2026-03-12

init

array

---

Problem:

P41 First Missing Positive

https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked

An obvious solution:

#include <vector>
#include <unordered_set>
#include <climits>

using std::vector;
using std::unordered_set;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i;
                unordered_set<int> uset;
                for (int num : nums) {
                        if (num > 0)
                                uset.insert(num);
                }

                for (i = 1; i < INT_MAX; i++) {
                        if (!uset.count(i)) {
                                break;
                        }
                }

                return i;
        }
};

In fact, for an array of length N, the smallest missing positive integer can only be in[1,N+1], so it can be optimized to:

#include <vector>
#include <unordered_set>
#include <climits>

using std::vector;
using std::unordered_set;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i, n;
                unordered_set<int> uset;
                for (int num : nums) {
                        if (num > 0)
                                uset.insert(num);
                }
                n = uset.size();

                for (i = 1; i <= n + 1; i++) {
                        if (!uset.count(i)) {
                                break;
                        }
                }

                return i;
        }
};

Official solution:

Think carefully, why do we use a hash table? Because a hash table is a data structure that supports fast lookup: given an element, we can check in O(1) time whether it is in the hash table. Therefore, we can consider designing the given array as a ‘substitute product’ of a hash table.

In fact, for an array of length N, the smallest missing positive integer can only be in[1,N+1]. This is because if[1,N]all appear, then the answer isN+1, otherwise the answer is[1,N]the smallest positive integer that does not appear in . In this way, we put all numbers in[1,N]numbers in the range into a hash table, we can also get the final answer. And the given array happens to have length N, which gives us an idea of designing the array as a hash table:
We traverse the array. For the number x encountered, if it is in[1,N]range, then mark the (x-1)-th position in the array (note: array indices start from 0). After the traversal, if all positions are marked, then the answer is N+1; otherwise, the answer is the smallest unmarked position plus 1.

So how to design this ‘mark’? Since the numbers in the array have no restrictions, this is not an easy task. But we can continue to use the property mentioned above: since we only care about numbers in [1,N], we can first traverse the array and modify numbers not in the range [1,N] to any number greater than N (for example, N+1). In this way, all numbers in the array become positive, so we can represent the ‘mark’ as a ‘negative sign’.

#include <vector>
#include <cmath>
#include <climits>

using std::vector;

class Solution {
    public:
        int firstMissingPositive(vector<int> &nums)
        {
                int i, n = nums.size();
                // Change all numbers less than or equal to 0 to n+1
                for (i = 0; i < n; i++) {
                        if (nums[i] <= 0) {
                                nums[i] = n + 1;
                        }
                }

                for (i = 0; i < n; i++) {
                        if (std::abs(nums[i]) <= n && nums[std::abs(nums[i]) - 1] > 0) { // 1..=n
                                nums[std::abs(nums[i]) -1] *= -1;
                        }
                }

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