41. First Missing Positive

Q: Why is the answer always in [1, n+1]?

An array of length n can contain at most n distinct positive integers in [1, n]. If all of 1..n are present, the first missing positive is n+1. If any is missing, the first missing is somewhere in [1, n].

Q: Why doesn't the while loop make the algorithm O(n²)?

Each swap permanently places at least one element in its correct position. Over all outer loop iterations, the total number of swaps across all while loop executions is ≤ n — amortised O(1) per iteration.

Q: What happens with duplicate values?

The while condition nums[nums[i]-1] !== nums[i] stops swapping when the target slot already holds the correct value — preventing an infinite loop on duplicates like [1,1].

hardAsked at Gusto

Find the smallest missing positive integer in O(n) time and O(1) extra space. Gusto asks this to test whether candidates can use the array itself as a hash map — the insight that the answer must lie in [1, n+1] is what unlocks the in-place solution.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Gusto loops.

Glassdoor (2025-08)— Cited in Gusto senior SWE reports as a hard problem that appears rarely but tests deep algorithmic creativity with constraints.
Blind (2025-06)— Gusto threads mention First Missing Positive as a hard that distinguishes candidates who can think about constraints creatively.

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.

Constraints

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

Examples

Example 1

Input

nums = [1,2,0]

Output

Explanation: Positive integers 1 and 2 are present. 3 is the first missing positive.

Example 2

Input

nums = [3,4,-1,1]

Output

Explanation: 1 is present, 2 is missing.

Example 3

Input

nums = [7,8,9,11,12]

Output

Explanation: 1 is missing — smallest positive not in the array.

Approaches

1. Array as hash map (index marking)

The answer is in [1, n+1]. Place each number in its 'correct' index position (num at index num-1) via swapping. Then scan for the first index where nums[i] != i+1 — that index+1 is the answer.

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

function firstMissingPositive(nums) {
  const n = nums.length;
  // Step 1: place each number in its correct position
  for (let i = 0; i < n; i++) {
    // swap nums[i] to its correct slot while valid
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIdx = nums[i] - 1;
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    }
  }
  // Step 2: find the first position where nums[i] != i+1
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  // All positions 1..n are filled — answer is n+1
  return n + 1;
}

Tradeoff: O(n) time, O(1) space. Each element is swapped at most once (total O(n) swaps across all iterations of the outer loop — the while loop doesn't multiply complexity). The while condition guards against cycles.

Gusto-specific tips

Lead with the key insight: 'The first missing positive must be in the range [1, n+1] because if all numbers 1..n were present, the answer would be n+1.' This bounds the search and justifies using the array of length n as a hash table indexed from 1 to n. The while loop terminates because each swap moves at least one element to its correct position — total swaps ≤ n. Gusto will likely ask you to trace through example [3,4,-1,1] step by step.

Common mistakes

Using a separate Set — O(n) space, violates the O(1) constraint.
Sorting the array — O(n log n), violates the O(n) constraint.
Swapping without the cycle guard (nums[nums[i]-1] !== nums[i]) — infinite loop when duplicates appear at the correct position.
Treating the answer range as [0, n] instead of [1, n+1] — missing positives are strictly positive integers.

Follow-up questions

An interviewer at Gusto may pivot to one of these next:

What if the array is read-only — how would you solve it with O(n) space?
Find the smallest missing non-negative integer (include 0).
Extend to find the k-th missing positive integer.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the answer always in [1, n+1]?

An array of length n can contain at most n distinct positive integers in [1, n]. If all of 1..n are present, the first missing positive is n+1. If any is missing, the first missing is somewhere in [1, n].

Why doesn't the while loop make the algorithm O(n²)?

Each swap permanently places at least one element in its correct position. Over all outer loop iterations, the total number of swaps across all while loop executions is ≤ n — amortised O(1) per iteration.

What happens with duplicate values?

The while condition nums[nums[i]-1] !== nums[i] stops swapping when the target slot already holds the correct value — preventing an infinite loop on duplicates like [1,1].

Practice these live with InterviewChamp.AI

Drill First Missing Positive and other Gusto interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →