Skip to main content

97. First Missing Positive

hardAsked at Datadog

Find the smallest missing positive integer in O(n) time and O(1) space. Datadog uses this for the index-as-hash trick — same shape as their dense-key occupancy check across a metric-ID space.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — index-as-hash analog.

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

Sort; first positive integer missing.

Time
O(n log n)
Space
O(1)
// Sort; iterate to find smallest positive not present.

Tradeoff: Sort cost violates O(n).

2. Cyclic in-place sort (optimal)

Pass 1: for each i, while nums[i] is in [1, n] and nums[i] != nums[nums[i]-1], swap to its 'home' position. Pass 2: first i 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[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) — each swap places one value home; total swaps <= n. Datadog-canonical.

Datadog-specific tips

Datadog grades on the index-as-hash insight: positive integer k belongs at index k-1. After sorting in place, the first index where nums[i] != i+1 reveals the missing positive.

Common mistakes

  • Using if instead of while — single pass over each cell, misses cascading swaps.
  • Swapping when nums[nums[i]-1] === nums[i] — infinite loop on duplicates.
  • Treating negatives or out-of-range — they should be ignored.

Follow-up questions

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

  • Missing Number (LC 268) — simpler variant.
  • Find All Duplicates (LC 442) — same in-place pattern.
  • Datadog-style: dense-key occupancy check.

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 inner while loop?

Each swap places one value at its home position. After that, it won't be touched. Total swaps across all iterations <= n.

Why answer in [1, n+1]?

If 1..n all present, the answer is n+1. Otherwise some k in [1, n] is missing.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →