Skip to main content

94. First Missing Positive

hardAsked at Reddit

Find the smallest missing positive integer in O(n) time and O(1) space. Reddit uses this for the cyclic-sort trick — clever in-place manipulation relevant to compact range-checks during shard-key allocation.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site, often as a 'pick your favorite' question.

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 constant extra 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. Sort + scan

Sort; walk; track expected.

Time
O(n log n)
Space
O(1)
// Fails the O(n) requirement.

Tradeoff: Doesn't satisfy constraints.

2. Cyclic sort (place value v at index v-1) (optimal)

Walk; while nums[i] is in [1, n] and not in place, swap to nums[nums[i]-1]. Final pass: 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[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: O(n) overall — each swap places a number permanently. Reddit interviewers love this trick.

Reddit-specific tips

Reddit interviewers want the cyclic sort. Bonus signal: argue why it's O(n) — each successful swap places a number in its 'home' position; total swaps bounded by n.

Common mistakes

  • Using if instead of while inside the loop (must keep swapping until current cell is settled).
  • Forgetting the duplicate check (nums[nums[i] - 1] !== nums[i]).
  • Returning -1 instead of n + 1 when all 1..n present.

Follow-up questions

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

  • Find all missing numbers (LC 448).
  • Find duplicates (LC 442).
  • Find the duplicate number (LC 287).

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 this O(n) and not O(n^2)?

Each swap places a number into its final spot. The total number of successful swaps is bounded by n.

Why answer = n + 1 when all present?

All of 1..n are accounted for, so the smallest missing is n + 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →