[LeetCode] 41. First Missing Positive

Table of Contents

Description

Given an unsorted integer array nums. Return the smallest missing positive integer that is not present in nums.

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 \leq \text{nums.length} \leq 10^5$
• $-2^{31} \leq \text{nums}[i] \leq 2^{31} - 1$

Approach

We use the nums array itself to keep track of which positive numbers are present. The key observation is that for an array of length n, the smallest missing positive integer must be between 1 and n+1. By modifying the array in-place—either by rearranging elements or marking them—we can record which numbers in this range exist without using extra space. This works because each index in the array can represent the presence of a number, allowing us to quickly identify the first missing positive by scanning the array after processing.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  // Upper bound for valid positive integers
  const maxPossibleMissing = nums.length + 1;

  for (let i = 0; i < nums.length; i++) {
    // Place nums[i] in its correct position if possible
    while (
      nums[i] > 0 &&
      nums[i] < maxPossibleMissing &&
      nums[nums[i] - 1] !== nums[i]
    ) {
      const correctIndex = nums[i] - 1;
      // Swap nums[i] with the number at its correct position
      [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
    }
  }

  // After rearrangement, the first place where nums[i] != i + 1 is the missing positive
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }

  // If all positions are correct, then missing positive is n + 1
  return maxPossibleMissing;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n)$. Each element is moved at most once to its correct position, and we make a constant number of passes through the array.

Space Complexity

The space complexity is $O(1)$. The algorithm only uses a constant amount of extra variables and modifies the nums array in-place.