First Missing Positive

Difficulty: Hard

Problem

Looking at an unsorted integer array nums, find the smallest positive integer (1, 2, 3, ...) that does not occur in it. The algorithm must take O(n) time and use only O(1) extra space.

Example

Input: nums = [5, 1, 2, 3, -2, 6]
Output: 4
Explanation: The positive values present include 1, 2, 3, 5, 6. Counting up from 1, the first one absent is 4.

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)

Pseudocode

function firstMissingPositive(nums):
    n = length(nums)
    for i from 0 to n-1:
        while nums[i] >= 1 AND nums[i] <= n
              AND nums[nums[i]-1] != nums[i]:
            swap nums[i] with nums[nums[i]-1]
    for i from 0 to n-1:
        if nums[i] != i+1:
            return i+1
    return n+1

Hints

  • Only positive values in range [1, n] matter
  • The answer is always in the range [1, n+1]
  • Use cyclic sort: place value x at index x-1

Complexity questions

Why can the answer be at most n+1?

Because there are only n slots, so if 1..n exist then n+1 is missing. With n array positions, we can hold at most values 1..n. If all are present, the smallest missing positive is n+1.

Why is the cyclic sort approach O(n) despite nested loops?

The inner while loop runs at most n times total. Each element is swapped at most once to its final position. The inner while loop's total iterations across all i values is O(n).

What's the space advantage of cyclic sort over hash set?

Cyclic sort uses O(1) space, hash set uses O(n). Cyclic sort modifies the array in-place, using only O(1) auxiliary space. Hash set requires O(n) space to store elements.

Check your understanding of First Missing Positive

Which numbers matter for this problem?

Only positive integers. We are looking for the smallest missing positive integer, so non-positive values can be ignored.

For an array of length n, where can the answer lie?

Between 1 and n+1. If all positives 1..n are present, the answer is n+1. Otherwise it is within 1..n.

Why is value 100 useless in an array of size 4?

The answer must be in [1, 5], so 100 doesn't affect it. For n=4, the answer is at most 5. Values > n cannot be the missing positive we seek, so they're irrelevant.

Related problems

Keep practising