First Missing Positive

ARRAYS & HASHING · HARD

The problem

You’re given an unsorted integer array nums — it can contain negatives, zeros, duplicates, and positives in any order, any range. Find the smallest positive integer that is not present in the array. For example, [3, 4, -1, 1] is missing 2 (1 is there, 2 isn’t) → answer 2. [1, 2, 0] has 1 and 2 but not 3 → answer 3. [7, 8, 9, 11, 12] doesn’t even contain 1 → answer 1. The array’s own negatives, zeros, and duplicates never count as “missing” candidates — only positive integers do.

LeetCode: First Missing Positive

Solution 1: Brute force — hash set + linear probe

The most direct reading of the problem: drop every value from nums into a Set so membership checks are O(1), then walk candidates k = 1, 2, 3, ... upward and ask the set “do you have k?” The first k the set doesn’t have is the answer. This is correct and runs in O(n) time — but it pays for that speed with an entirely separate O(n)-sized data structure. It’s not “brute force” in the slow-time sense; it’s brute force in the sense of “the first thing you’d reach for,” and it trades space for simplicity.

Interactive visualization

Bars show nums for a small example — the same values verified above. Watch the probe walk k upward (bars are only ever read here, never rearranged).

nums = [3, 4, -1, 1]

Press Play or Step to begin.

Step 0 / 7

The code

function firstMissingPositiveBrute(nums) {
  const set = new Set(nums);
  let k = 1;
  while (set.has(k)) {
    k++;
  }
  return k;
}

Line by line:

new Set(nums) copies every value — negatives, zeros, duplicates, positives, everything — into a hash set in one pass. Duplicates collapse automatically; irrelevant values (negatives, zero) just sit in the set unused, they’re harmless.
k starts at 1 because the problem only ever asks about positive integers — 0 and negatives can never be “the answer.”
while (set.has(k)) k++ — as long as the set has this candidate, it can’t be the missing one, so move to the next candidate. The loop stops the instant it finds a gap.
Why this terminates quickly: an array of length n can contain at most n distinct positive values in the range [1, n], so the probe can never run past k = n + 1 before finding a miss — the loop body runs at most n + 1 times total, keeping this O(n).

Complexity

Time	Space	Approach
O(n)	O(n)	Hash set membership + linear probe

Solution 2: Optimal — in-place index-as-hash placement

The set in Solution 1 exists only to answer “is value v present?” quickly. The key insight: if the answer must be somewhere in [1, n+1] (proven above), then nums itself — an array of exactly n slots — is big enough to be that hash set, using each index as the “bucket” for the value it should hold. Value v’s correct home is index v - 1. So walk the array once, and for every value that’s in range and not already sitting in its correct home, swap it there — repeating at that same position until whatever lands there is either out of range or already correctly placed. After this placement pass, scan once more: the first index i where nums[i] !== i + 1 means i + 1 is missing. If every slot matches, the array is a perfect run 1..n and the answer is n + 1.

Interactive visualization

Same example as Solution 1 — watch values physically swap into their “home” index (value v at index v - 1), then a final scan finds the first mismatch.

nums = [3, 4, -1, 1]

Press Play or Step to begin.

Step 0 / 14

The code

function firstMissingPositiveOptimal(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 target = nums[i] - 1;
      [nums[i], nums[target]] = [nums[target], nums[i]];
    }
  }

  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

Line by line:

nums[i] > 0 && nums[i] <= n — only values that COULD ever be the answer are worth placing. Anything ≤ 0 or > n can never be the smallest missing positive (proven above: the answer is always in [1, n+1]), so those values are simply left wherever they sit.
nums[nums[i] - 1] !== nums[i] — this is the duplicate/already-placed guard. It asks “is the value already sitting in its own home?” If target already holds this exact value (a duplicate, or it’s already correctly placed), swapping would just trade the value with itself or bounce two copies back and forth forever — so skip it and move on. This one condition is what prevents the infinite loop that this swap pattern is notorious for.
[nums[i], nums[target]] = [nums[target], nums[i]] — destructuring assignment swap. Both sides of the RHS array literal are evaluated (reading the OLD values) before either assignment happens, so this is safe even though target was computed from the very value about to be overwritten. (See the trick question below for what breaks if you write this swap the naive way instead.)
The while, not if, matters: after a swap, index i holds a brand-new value that also needs checking — keep swapping at i until whatever lands there is out of range or already home, THEN move to i + 1.
The final scan’s first mismatch nums[i] !== i + 1 is the answer, because the placement pass guarantees every value that legitimately belongs in [1, n] made it to its home index if it was present at all — a mismatch can only mean that value was never in the array.
If the scan finds no mismatch, nums holds exactly 1..n with nothing missing in range, so the smallest missing positive is the next integer up, n + 1.

Why the nested loop is still O(n), not O(n²): it looks quadratic — a for with a while inside it — but the two loops don’t multiply the way they would in, say, nested comparisons. Every single swap permanently places one value into its correct home index, and a value is never moved again once it’s home (the guard condition stops touching indices that already hold their correct value). There are only n indices total, so there can be at most n swaps across the entire outer loop, combined — not per iteration. The outer loop contributes O(n) steps and the inner while contributes at most O(n) swaps in total across all of those steps, so the whole placement pass is O(n) + O(n) = O(n), and the final scan adds another O(n). Three O(n) phases summed is still O(n).

Complexity

Time	Space	Approach
O(n)	O(1)	In-place index-as-hash placement, then scan

Complexity comparison

Solution	Time	Space
Brute force (hash set + probe)	O(n)	O(n)
Optimal (in-place placement)	O(n)	O(1)

Be honest about what actually improved here: both solutions are O(n) time — there’s no asymptotic time win to claim. The real story is space. Solution 1 pays for its O(1) membership checks with an entire separate hash set sized to the input. Solution 2 gets the same O(1)-style lookup (“is value v present, and where”) for free by reusing nums’s own indices as the hash table, dropping extra space from O(n) to O(1) — at the cost of mutating the input array, which isn’t always acceptable in a real API.

Interview corner

Why must the answer always lie in [1, n+1], where n is the array length — before you even look at a single value?

An array of length n can hold at most n distinct values.
If every one of 1, 2, ..., n happens to be present (using up all n slots on exactly those values), the smallest missing positive is n + 1 — there’s no room left for it to be anything smaller.
If even one of 1..n is absent, that gap is smaller than n + 1 and wins. Either way, the answer never needs to be searched for past n + 1 — which is exactly why the hash-set probe in Solution 1 terminates in at most n + 1 steps, and why Solution 2 only needs n index slots to represent every value that could possibly matter.

Why is the guard nums[nums[i] - 1] !== nums[i] the specific thing that prevents an infinite loop with duplicate values?

Without it, an array like [1, 1] would try to swap index 0’s value (1, whose home is index 0) with itself forever — nums[i] and nums[target] are literally the same slot, or hold the same value, so the swap changes nothing and the while condition never becomes false on its own.
The guard explicitly asks “does the target slot already hold this value?” before swapping. If it does — whether because this value is already home, or because a duplicate already claimed that home — swapping is pointless, so the loop exits instead of spinning.
This is the exact detail that separates a correct in-place placement pass from a classic infinite-loop bug — it’s worth stating explicitly in an interview rather than hoping the interviewer doesn’t ask “what if there are duplicates?”

↳ Common follow-up: “Walk me through [1, 1] by hand.” At i = 0: nums[0] = 1, target = 0, nums[0] === nums[0] is true → guard fails → no swap, move to i = 1. At i = 1: nums[1] = 1, target = 0, nums[0] === nums[1] (both are 1) → guard fails again → no swap. Final scan: index 0 matches (1), index 1 doesn’t (nums[1] = 1 !== 2) → answer is 2. Correct, and no infinite loop.

The problem statement usually asks for O(1) auxiliary space. Does mutating the input array count against that?

By the convention LeetCode (and most interviewers) use for “O(1) extra space,” no — the input array itself isn’t counted, since it already exists; “extra” space means space beyond the input.
Solution 2 uses a constant number of local variables (i, target, loop counters) regardless of n — that’s genuinely O(1) auxiliary space.
It’s still worth flagging out loud in an interview: this technique permanently reorders the caller’s array as a side effect. If the caller needs their original order preserved, you’d need to copy first — which brings space back to O(n) and defeats the purpose, so it’s a real design tradeoff, not a free lunch.

Trick question — what does this log?

const nums = [3, 4, -1, 1];
const i = 0;
const target = nums[i] - 1;
nums[i] = nums[target];
nums[target] = nums[i];
console.log(nums);

Answer: [ -1, 4, -1, 1 ] — NOT the correctly swapped [ -1, 4, 3, 1 ] you’d get from the destructuring version above.
target is nums[0] - 1 = 2. The naive two-line swap overwrites nums[0] first (nums[0] = nums[2], i.e. -1), THEN reads nums[i] again for the second line — but nums[i] is now -1, not the original 3. So nums[2] = nums[i] writes -1 right back into index 2, and the original value 3 is gone entirely, never having reached its home.
This is exactly why the real solution above uses [nums[i], nums[target]] = [nums[target], nums[i]] — a destructuring swap evaluates the entire right-hand side array literal (both old values) BEFORE assigning either side, so neither value is lost even though one assignment depends on the pre-swap state of the other.

⚠ Trap: this bug is easy to miss in review because the array still “looks plausible” afterward — no crash, no obviously wrong shape, just a silently corrupted value. In this problem specifically it would produce a wrong final answer with no error message at all.

Quiz

Why is it guaranteed that the answer is always somewhere in [1, n+1], where n is the array’s length?
- An array of length n has room for at most n distinct values, so the answer can never need to be larger than n+1
- It’s only true if the array happens to already be sorted
- It isn’t guaranteed — the answer could be arbitrarily large depending on the input
What is the actual complexity tradeoff between the hash-set solution and the in-place solution?
- Same O(n) time for both — the real difference is O(n) vs O(1) extra space
- The in-place solution is asymptotically faster in time, O(n) vs O(n²)
- The hash-set solution uses less space because Sets are more compact than arrays
What specifically stops the in-place solution from looping forever on an array like [1, 1]?
- The guard checks whether the target index already holds this exact value, and skips the swap if so
- A hard iteration limit is built into the while loop to force it to stop
- Nothing special — duplicate values can never actually occur in valid LeetCode input
Why is the nested for/while placement pass O(n) overall, not O(n²)?
- Each swap places a value into its final home for good, so the total number of swaps across the whole run is capped at n, not n per outer step
- It isn’t O(n) — this solution is genuinely O(n²), just with a small constant factor
- It’s only O(n) for small arrays; larger inputs degrade to O(n²)
Why does the swap use destructuring assignment ([nums[i], nums[target]] = [nums[target], nums[i]]) instead of two plain assignment lines?
- A naive two-line swap overwrites nums[i] before the second line can read its original value, silently losing data — destructuring reads both old values first
- Destructuring is purely a performance optimization with no correctness difference
- It’s a stylistic choice only — both forms behave identically in every case