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]range, 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? This is because a hash table is a data structure that supports fast lookup: given an element, we can check in O(1) time whether the element is in the hash table. Therefore, we can consider designing the given array as a ‘substitute’ for a hash table.

In fact, for an array of length N, the smallest missing positive integer can only be in[1,N+1]range. 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 [1,N]. In this way, we put all numbers in[1,N]range into a hash table, we can also get the final answer. And since the given array has exactly length N, this gives us an idea of designing the array as a hash table:
We traverse the array. For each 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 do we 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 change numbers not in the [1,N] range 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
        }
};