Skip to main content

88. First Missing Positive

hardAsked at Snowflake

Find the smallest missing positive integer in O(n) time and O(1) space. Snowflake asks this for the cyclic-placement trick — relevant to building dense column-id mappings during data ingestion.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake metadata-team uses this in onsites.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-II screens.

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. Sort and scan

Sort. Walk; track expected next positive.

Time
O(n log n)
Space
O(1) in-place sort
// outline — n log n, violates O(n) requirement.

Tradeoff: Too slow.

2. Cyclic placement (optimal)

Place each value v in [1, n] at index v-1 via swaps. Final scan: first index i where nums[i] != i+1 gives missing = 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] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
  return n + 1;
}

Tradeoff: Linear total work — each swap places one element correctly. The while loop's amortized cost is O(1) per index.

Snowflake-specific tips

Snowflake interviewers want the cyclic-placement insight: 'every swap places one element correctly, so total swaps <= n'. Bonus signal: connect to dense column-id assignment — when Snowflake assigns sequential IDs to columns during ingestion, finding the first unused ID uses a similar in-place mapping.

Common mistakes

  • Using a for-loop with i++ instead of while — fails to repeatedly fix index i after swap brings new value.
  • Forgetting the duplicate-guard (nums[nums[i]-1] !== nums[i]) — infinite loop on duplicates.
  • Comparing against i instead of i+1 in the final check.

Follow-up questions

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

  • Find All Numbers Disappeared in an Array (LC 448).
  • Find the Duplicate Number (LC 287).
  • How does Snowflake assign sequential column IDs?

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 the duplicate guard?

Without it, two equal values would swap forever. The guard ensures we only swap when the destination doesn't already have the right value.

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

Pigeonhole: n integers can occupy at most n distinct positive slots. The smallest missing is in [1, n+1]; if all 1..n are present, the answer is n+1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →