Skip to content

First Missing Positive⚓︎

Link

Description⚓︎

Given an unsorted integer array nums, return the smallest missing positive integer.

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

Example 1:

  • Input: nums = [1,2,0]
  • Output: 3
  • Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

  • Input: nums = [3,4,-1,1]
  • Output: 2
  • Explanation: 1 is in the array but 2 is missing.

Example 3:

  • Input: nums = [7,8,9,11,12]
  • Output: 1
  • Explanation: The smallest positive integer 1 is missing.

Constraints:

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

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }

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

Step 1: Rearrange the Array

  • Iterate through each element in the array using a loop.
  • For each element nums[i], if it is a positive integer and within the range [1, n] (inclusive) and is not already in its correct position (i.e., nums[nums[i] - 1] != nums[i]), then swap it with the element at its "correct" position (nums[nums[i] - 1]).
  • This swapping continues in a while loop until either the current element is negative, out of the range [1, n], or already in its correct position. This ensures that, at the end of this step, every positive integer x that is less than or equal to n and appears in the array is placed at index x-1.

Step 2: Find the Missing Integer

  • After rearranging, iterate through the array again.
  • Check if nums[i] is equal to i + 1 for each i. If for any i, nums[i] != i + 1, it means i + 1 is the smallest missing positive integer, so return i + 1.
  • If all positions are correctly occupied, it means the array contains all integers from 1 to n. Therefore, the smallest missing positive integer is n + 1.