Skip to main content

87. First Missing Positive

hardAsked at Plaid

Find the smallest missing positive integer in O(n) time and O(1) space. Plaid asks this because finding the next available transaction-id in a partially-allocated id-pool is exactly this primitive.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — id-pool allocation.
  • LeetCode Discuss (2026)— Plaid hard array problem.

Problem

Given an unsorted integer array nums, return the smallest 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.

Constraints

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

Examples

Example 1

Input
nums = [1,2,0]
Output
3

Example 2

Input
nums = [3,4,-1,1]
Output
2

Example 3

Input
nums = [7,8,9,11,12]
Output
1

Approaches

1. Hash set lookup

Put nums in a set; scan 1, 2, 3, ... until missing.

Time
O(n)
Space
O(n)
function firstMissingPositive(nums) {
  const s = new Set(nums);
  for (let i = 1; ; i++) if (!s.has(i)) return i;
}

Tradeoff: Violates O(1) space.

2. In-place cyclic sort

Swap each value to its 'correct' index (i.e., put k at position k-1). Then scan for the first index where nums[i] != i+1.

Time
O(n)
Space
O(1)
function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

Tradeoff: Linear time amortized — each swap places at least one value correctly. The check 'nums[nums[i]-1] !== nums[i]' prevents infinite loop on duplicates.

Plaid-specific tips

Plaid grades this on whether you spot 'the answer must be in [1, n+1].' Bonus signal: walk through the swap-until-fixpoint invariant — each iteration either places a value correctly or determines it's out of range. Connect to id-pool allocation where you're searching for the lowest unallocated id within a contiguous range.

Common mistakes

  • Using if instead of while — single swap doesn't fully sort.
  • Forgetting the duplicate-check — infinite loop on [1, 1].
  • Off-by-one: 'correct' position for value k is index k-1.

Follow-up questions

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

  • All missing positives in O(n).
  • Find the kth missing positive.
  • Same problem on a stream — bounded memory.

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 in [1, n+1]?

If all of 1..n are present, the answer is n+1. Otherwise some value in 1..n is missing.

Why amortized O(n)?

Each swap places at least one value at its correct index, which won't be swapped again. Total swaps <= n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →