Skip to main content

87. First Missing Positive

hardAsked at Salesforce

Find the smallest positive integer missing from an unsorted array in O(n) time and O(1) space. Salesforce uses this as an O(1)-space cyclic-sort stress test.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses cyclic sort in their ID-assignment logic for new records.
  • Blind (2025-09)— Hard L5+ onsite question.

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. Set lookup

Insert all values into a set; check 1, 2, 3, ... until missing.

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

Tradeoff: O(n) space — fails the explicit constraint.

2. Cyclic sort in place

For each position i, swap nums[i] to its correct position (nums[i] - 1) if valid. Then scan: first index where nums[i] !== i+1 is the answer.

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[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

Tradeoff: O(1) extra space. The cyclic-sort puts each valid value at its 'natural' index. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses cyclic sort in their ID-assignment logic — find the smallest available ID in a bounded range without an external counter. They specifically grade on whether you can articulate WHY swapping works (each swap places one element correctly, so total swaps are at most n). Bonus signal: explain the amortized O(n) bound.

Common mistakes

  • Using if instead of while — only one swap per position; misses subsequent good swaps.
  • Forgetting the `nums[nums[i] - 1] !== nums[i]` check — infinite loop on duplicates.
  • Skipping bounds checks (1 <= nums[i] <= n) — out-of-bounds access.

Follow-up questions

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

  • Find All Numbers Disappeared in an Array (LC 448) — same cyclic-sort pattern.
  • Find the Duplicate Number (LC 287).
  • First Missing Positive in a stream.

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 O(n) despite the while loop?

Amortized analysis: each swap places at least one element at its correct position. Over the whole loop, at most n swaps happen. The while ensures we keep working until the current position is settled.

Why ignore negatives and >n values?

The answer is in [1, n+1]. Values outside that range can't be the answer and can be ignored during placement.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →