First Missing Positive

Difficulty: Hard

Problem

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

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: The positive integers present are 1, 3, 4. The smallest missing positive is 2.

Brute-force approach

Try candidate values 1, 2, 3... and scan the entire array for each candidate.

Steps

  1. Set candidate = 1
  2. Scan the entire array to check if candidate exists
  3. If found, increment candidate and repeat
  4. If not found, return candidate as the answer

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • For each candidate, we scan the entire array
  • Too slow for large n (millions of operations)
  • Doesn't meet the O(n) time requirement

Optimal approach

Key insight: Value x belongs at index x-1. Rearrange the array in-place, then find the first mismatch.

Two approaches: Hash Set (O(n) space) or Cyclic Sort (O(1) space).

Steps

  1. Place each number at its correct index (value x at index x-1)
  2. Scan the array to find the first position where nums[i] ≠ i+1
  3. Return n+1 if all positions match correctly

Time complexity: O(n) · Space complexity: O(1)