Skip to main content

99. First Missing Positive

hardAsked at Workday

Find the smallest missing positive integer in O(n) and O(1) space. Workday uses this for array-as-hash-map fluency — same shape as finding the next unassigned employee ID in a partially-allocated range.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE3 onsite.

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

Add all to a set, iterate 1, 2, 3...

Time
O(n)
Space
O(n)
// fails O(1) space

Tradeoff: Easy but uses linear extra space.

2. Cyclic sort (place i at index i-1)

For each index, swap nums[i] into position nums[i]-1 if valid. Then scan for 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[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) space by using the array as a hash map. The cyclic sort places each value at its correct index. The 'nums[nums[i] - 1] !== nums[i]' guard prevents infinite loops on duplicates.

Workday-specific tips

Workday wants the cyclic sort. The duplicate guard is the trick — without it, two equal values cause infinite swap. Walk through this guard out loud. The answer is bounded by n+1 (pigeonhole).

Common mistakes

  • Forgetting the duplicate guard — infinite loop.
  • Using a set or sort — violates space or time constraint.
  • Forgetting to return n+1 when [1, 2, 3, ..., n] is present.

Follow-up questions

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

  • Find All Numbers Disappeared in an Array (LC 448).
  • Find the Duplicate Number (LC 287).
  • What if duplicates aren't allowed?

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 bounded by n+1?

If all values in [1, n] are present, the answer is n+1. If any value in [1, n] is missing, the answer is at most n. So the search range is [1, n+1].

Why cyclic sort?

We want value v at index v-1. Cyclic sort places each value at its correct slot in O(n) total by swapping. Then a linear scan finds the first mismatch.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →