Skip to main content

41. First Missing Positive

hardAsked at GoDaddy

Find the smallest missing positive integer in O(n) time and O(1) extra space — GoDaddy's domain-registry team applies this index-as-hash-bucket pattern when allocating the next available numeric ID from a sparse, unsorted pool of existing registrations.

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

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
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

Store all positive numbers in a Set; scan from 1 upward for the first miss. O(n) time but O(n) space.

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:

2. Index-as-bucket (in-place cyclic sort)

Use the array itself as a hash table: place each number n at index n-1 if 1 <= n <= length; 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]) {
      const dest = nums[i] - 1;
      [nums[i], nums[dest]] = [nums[dest], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

Tradeoff:

GoDaddy-specific tips

GoDaddy's hard rounds explicitly probe the O(1) space constraint — the hash-set solution is disqualified if the interviewer enforces it. Practice explaining the cyclic-sort invariant: the while-loop terminates because every swap moves at least one number to its correct bucket, giving amortized O(n) total swaps.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →