First Missing Positive (LeetCode 41)
You will see how an array of n values can serve as its own hash table: each value from 1 to n is swapped to index v - 1.
You get an array of integers, nums, in no particular order. It may hold zeros, negative numbers, very large numbers and repeated values. Find the smallest positive whole number (1, 2, 3, ...) that does not appear anywhere in nums, and return it.
Your solution must run in O(n) time, where n is the length of nums, and use only O(1) extra memory beyond the input array. Changing the values inside nums is allowed.
Worked Examples
nums = [1,2,0]3nums = [3,4,-1,1]2nums = [7,8,9,11,12]1⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Why It Works & Core Invariant
A value v from 1 to n belongs at index v - 1, so the array can be its own hash table: send each such value home, and the first index that does not hold its own value names the smallest missing positive. Every other value can be ignored, because the answer is always between 1 and n + 1.
Real-World Scenario & Production Applications
Handing out the lowest free number: POSIX requires open() to return the lowest file descriptor that is not in use, and seat, locker or worker-slot numbers are often reused the same way. The numbers in use already say which slot each one fills, so the first empty slot is the answer.
Step-by-Step Execution Trace Table
Example 2, nums = [3,4,-1,1] (n = 4):
| Step | i | Value nums[i] | Home nums[i] - 1 holds | Action | nums after |
|---|---|---|---|---|---|
| 1 | 0 | 3 | -1 | swap: 3 goes home to index 2 | [-1,4,3,1] |
| 2 | 0 | -1 | (no home) | stop: -1 is not in 1..4 | [-1,4,3,1] |
| 3 | 1 | 4 | 1 | swap: 4 goes home to index 3 | [-1,1,3,4] |
| 4 | 1 | 1 | -1 | swap: 1 goes home to index 0 | [1,-1,3,4] |
| 5 | 1 | -1 | (no home) | stop | [1,-1,3,4] |
| 6 | 2 | 3 | 3 | stop: the home already holds 3 | [1,-1,3,4] |
| 7 | 3 | 4 | 4 | stop: the home already holds 4 | [1,-1,3,4] |
| 8 | scan | nums[0] = 1; nums[1] = -1, not 2 | return 2 |
Three swaps for four values: each swap put one value in its home for good. With a repeated value, such as the second 2 in [2,3,2,1], the home already holds a copy; the test nums[nums[i] - 1] != nums[i] stops there, while nums[i] != i + 1 would swap the two 2s forever.
| 1 | A value `v` from 1 to `n` has a home, index `v - 1`: the array can be its own hash table, and the answer is between 1 and `n + 1`. |
| 2 | Keep this true: an index that holds its own value keeps it, and each swap sends one more value home. |
| 3 | The shape: `for i in range(n):` with an inner loop that keeps moving the value at `i` to its home while it has one it does not fill yet; then a second loop over the indices, and a last return after it. |
| 4 | The trap: test whether the home already holds the value, `nums[nums[i] - 1] != nums[i]`, not `nums[i] != i + 1`, or a repeated value swaps forever. |
Target: First Missing Positive (LeetCode 41). `n` values fill at most the numbers 1 to `n`, so the answer is between 1 and `n + 1`, and only values from 1 to `n` need a home.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set would answer "is 1 here? is 2 here?" at once, but this problem allows no extra memory. Cyclic Sort makes the array its own set. A value v from 1 to n has a natural place, index v - 1: its home. Swap every such value into its home, and afterwards each index i either holds i + 1 (that number is present) or holds something else (that number is missing). The smallest missing positive is the first index that fails, plus one, or n + 1 when none fails: n values can fill at most the homes of 1 to n.
🧱 The Analogy: Numbered Lockers
Lockers numbered 1 to n stand in a row, and in front of each one waits a person with a ticket. If your ticket names a locker, you walk to it and swap places with whoever is there, unless that person already holds the same number. People with tickets like 0, -3 or 900 have no locker, so they stay wherever they are pushed. Once nobody can move, the first locker whose person holds a different number is the smallest number nobody had.
🪄 The Mathematical Harmony / Magic Trick
for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: home = nums[i] - 1 nums[i], nums[home] = nums[home], nums[i] Each swap puts one value into its home, and the while never moves a value that is home, so there are at most n swaps however the loops look. The test that ends the loop is about the home, not about i: when a repeated value finds its home already holding a copy, the swap would exchange two equal values and change nothing, and nums[nums[i] - 1] != nums[i] is what lets the loop stop.
💡 Summary
Swap each value v in 1..n to index v - 1 while its home does not hold it, then return the first i + 1 with nums[i] != i + 1, or n + 1. time (at most n swaps in all), extra space.
Testing the index instead of the home: loop while
nums[nums[i] - 1] != nums[i], not whilenums[i] != i + 1. With a repeated value, as in[1, 1], the home already holds a copy, the swap changes nothing, and the loop never ends.The one-line swap: save
home = nums[i] - 1first.nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]writesnums[i]before the second index is computed, so the value lands in the wrong place.Values with no home: test
1 <= nums[i] <= nbefore readingnums[nums[i] - 1]. A 0 or a negative value gives a negative index, which Python reads from the end of the list without an error.Testing the index instead of the value: the closing scan reads
nums[i] != i + 1, notnums[i] != i. A filled home holdsi + 1, the value that belongs there, not the bare indexi, so comparing againstialone would call every filled home missing.Forgetting
n + 1: when every home holds its value, as in[2, 1], the answer isn + 1 = 3, which no index names.
4-Phase Thought Process Model
You will see how a senior engineer hears "smallest missing positive, O(1) extra memory" and uses the array as its own hash table.
Pattern Recognition Signals
The 10-second spot
"The smallest positive whole number (1, 2, 3, ...) that does not appear anywhere in nums", "O(n) time" and "only O(1) extra memory beyond the input array": a missing number, with no room for a hash set, and "changing the values inside nums is allowed". Only 1 to n + 1 can be the answer, and each of 1 to n names an index, so the signal is Cyclic Sort: index v - 1 is the home of v.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
An index j that holds j + 1 keeps it, and every swap sends one more value v from 1 to n to its home v - 1; when the swaps end, the first i with nums[i] != i + 1 gives the answer i + 1, or n + 1 if there is none.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Loop on the home,
nums[nums[i] - 1] != nums[i], not onnums[i] != i + 1: in[2,3,2,1]the 2 at index 0 finds its home, index 1, already holding a 2, and the index test would swap the two 2s forever.Save
home = nums[i] - 1before swapping:nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]writesnums[i]first, then computes the second index from the new value.Check
1 <= nums[i] <= nbefore readingnums[nums[i] - 1]: a 0 or a negative value gives a negative index, which Python reads from the end of the list without an error, and a value abovenis past the end.Return
n + 1after the scan: whennumsholds every number from 1 ton, as in[2,1], no index is missing its value and the answer is 3.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Cyclic Sort and let the array be its own hash table. The answer has to be between 1 and n plus 1, because n values can cover at most the numbers 1 to n, so every other value can be ignored. Every value v from 1 to n has a home, index v minus 1. I walk the array, and while the current value has a home that doesn't hold it yet, I swap it there. Each swap sends one value home for good, so there are at most n swaps in total. Then I scan: the first index i whose value isn't i plus 1 gives the answer i plus 1, and if every home is filled it's n plus 1. The trap is the loop test: I check whether the home already holds v, not whether index i holds i plus 1, or a repeated value would swap forever. That's
O(N)time andO(1)extra space.
So: the answer is in 1..n + 1, each v in 1..n has the home v - 1, swap until every value is home or has none, then scan.
Complexity & Mathematical Proof
O(N)
The outer for i in range(n) runs N times. The inner while looks slow, but each pass of its body is one swap that sends a value v to index v - 1, which holds v from then on, and an index that holds its own value is never swapped again: the while test fails there. So at most N swaps happen in the whole run, not per i, and the loops together make at most 2N tests of the while condition. The second for reads each index at most once and stops at the first gap: O(N). Total: O(N).
O(1)
The swaps rearrange nums in place, and the code keeps only n, i and home: O(1) extra space, with no recursion. The answer is one integer.
T(N) = N (outer loop) + at most N swaps in all + N (scan) = O(N)
The outer for i in range(n) runs N times. The inner while looks slow, but each pass of its body is one swap that sends a value v to index v - 1, which holds v from then on, and an index that holds its own value is never swapped again: the while test fails there. So at most N swaps happen in the whole run, not per i, and the loops together make at most 2N tests of the while condition. The second for reads each index at most once and stops at the first gap: O(N). Total: O(N).
Derivation Progression
O(N)
for i in range(n) visits each index once; the while test runs once more than the swaps made at that i.
at most N
Each swap sends one value to its home v - 1 for good, and a value at home is never moved again, so the swaps across every i add up to at most N.
O(N)
The second for reads each index at most once and returns at the first i with nums[i] != i + 1.
O(N)
O(N) loop steps, at most N swaps and one scan.
Variable Definitions
Number of values, len(nums) (at most 10^5)
Memory Architecture & Bounds
O(1): no recursion
O(1): n, i, home
O(1): one integer
Boundary Best / Worst Cases
: no value has a home, as in [7,8,9,11,12], so no swap happens, but every index is still visited once
: a shuffled 1..N, where every value is swapped home once and the scan reads every index
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the smallest positive whole number", **"does not appear anywhere in nums"**, "only O(1) extra memory beyond the input array". A missing number among 1 to n with no room for a set: Cyclic Sort, each value v sent to index v - 1.
Up to values from to . A hash set of the values takes extra memory and sorting takes time, both outside the stated bounds; Cyclic Sort makes at most swaps in all, then one scan.
The input array is the scratch space: a caller that still needs the original order must pass a copy, which brings back the memory the method avoids, so document the mutation. With values from to , compute nums[i] - 1 only after checking 1 <= nums[i] <= n: in C or Java an unchecked index reads outside the array. The swaps jump to scattered positions, so on arrays much larger than the CPU cache each swap can be a cache miss, where a sequential scan is not.
Core Algorithmic State Invariants
A value `v` from 1 to `n` belongs at index `v - 1`. Zeros, negatives and values above `n` have no home and can stay anywhere, because the answer is between 1 and `n + 1`.
Swap while `nums[nums[i] - 1] != nums[i]`. With a repeated value the home already holds a copy, so testing `nums[i] != i + 1` would swap two equal values forever.
Each swap sends one value home for good, so the `while` makes at most `n` swaps in the whole run: O(N) time, and the array itself is the table, O(1) extra space.
First Missing Positive (LeetCode 41)
You will see how an array of n values can serve as its own hash table: each value from 1 to n is swapped to index v - 1.
You get an array of integers, nums, in no particular order. It may hold zeros, negative numbers, very large numbers and repeated values. Find the smallest positive whole number (1, 2, 3, ...) that does not appear anywhere in nums, and return it.
Your solution must run in O(n) time, where n is the length of nums, and use only O(1) extra memory beyond the input array. Changing the values inside nums is allowed.
Worked Examples
nums = [1,2,0]3nums = [3,4,-1,1]2nums = [7,8,9,11,12]1⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Why It Works & Core Invariant
A value v from 1 to n belongs at index v - 1, so the array can be its own hash table: send each such value home, and the first index that does not hold its own value names the smallest missing positive. Every other value can be ignored, because the answer is always between 1 and n + 1.
Real-World Scenario & Production Applications
Handing out the lowest free number: POSIX requires open() to return the lowest file descriptor that is not in use, and seat, locker or worker-slot numbers are often reused the same way. The numbers in use already say which slot each one fills, so the first empty slot is the answer.
Step-by-Step Execution Trace Table
Example 2, nums = [3,4,-1,1] (n = 4):
| Step | i | Value nums[i] | Home nums[i] - 1 holds | Action | nums after |
|---|---|---|---|---|---|
| 1 | 0 | 3 | -1 | swap: 3 goes home to index 2 | [-1,4,3,1] |
| 2 | 0 | -1 | (no home) | stop: -1 is not in 1..4 | [-1,4,3,1] |
| 3 | 1 | 4 | 1 | swap: 4 goes home to index 3 | [-1,1,3,4] |
| 4 | 1 | 1 | -1 | swap: 1 goes home to index 0 | [1,-1,3,4] |
| 5 | 1 | -1 | (no home) | stop | [1,-1,3,4] |
| 6 | 2 | 3 | 3 | stop: the home already holds 3 | [1,-1,3,4] |
| 7 | 3 | 4 | 4 | stop: the home already holds 4 | [1,-1,3,4] |
| 8 | scan | nums[0] = 1; nums[1] = -1, not 2 | return 2 |
Three swaps for four values: each swap put one value in its home for good. With a repeated value, such as the second 2 in [2,3,2,1], the home already holds a copy; the test nums[nums[i] - 1] != nums[i] stops there, while nums[i] != i + 1 would swap the two 2s forever.
| 1 | A value `v` from 1 to `n` has a home, index `v - 1`: the array can be its own hash table, and the answer is between 1 and `n + 1`. |
| 2 | Keep this true: an index that holds its own value keeps it, and each swap sends one more value home. |
| 3 | The shape: `for i in range(n):` with an inner loop that keeps moving the value at `i` to its home while it has one it does not fill yet; then a second loop over the indices, and a last return after it. |
| 4 | The trap: test whether the home already holds the value, `nums[nums[i] - 1] != nums[i]`, not `nums[i] != i + 1`, or a repeated value swaps forever. |
Target: First Missing Positive (LeetCode 41). `n` values fill at most the numbers 1 to `n`, so the answer is between 1 and `n + 1`, and only values from 1 to `n` need a home.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set would answer "is 1 here? is 2 here?" at once, but this problem allows no extra memory. Cyclic Sort makes the array its own set. A value v from 1 to n has a natural place, index v - 1: its home. Swap every such value into its home, and afterwards each index i either holds i + 1 (that number is present) or holds something else (that number is missing). The smallest missing positive is the first index that fails, plus one, or n + 1 when none fails: n values can fill at most the homes of 1 to n.
🧱 The Analogy: Numbered Lockers
Lockers numbered 1 to n stand in a row, and in front of each one waits a person with a ticket. If your ticket names a locker, you walk to it and swap places with whoever is there, unless that person already holds the same number. People with tickets like 0, -3 or 900 have no locker, so they stay wherever they are pushed. Once nobody can move, the first locker whose person holds a different number is the smallest number nobody had.
🪄 The Mathematical Harmony / Magic Trick
for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: home = nums[i] - 1 nums[i], nums[home] = nums[home], nums[i] Each swap puts one value into its home, and the while never moves a value that is home, so there are at most n swaps however the loops look. The test that ends the loop is about the home, not about i: when a repeated value finds its home already holding a copy, the swap would exchange two equal values and change nothing, and nums[nums[i] - 1] != nums[i] is what lets the loop stop.
💡 Summary
Swap each value v in 1..n to index v - 1 while its home does not hold it, then return the first i + 1 with nums[i] != i + 1, or n + 1. time (at most n swaps in all), extra space.
Testing the index instead of the home: loop while
nums[nums[i] - 1] != nums[i], not whilenums[i] != i + 1. With a repeated value, as in[1, 1], the home already holds a copy, the swap changes nothing, and the loop never ends.The one-line swap: save
home = nums[i] - 1first.nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]writesnums[i]before the second index is computed, so the value lands in the wrong place.Values with no home: test
1 <= nums[i] <= nbefore readingnums[nums[i] - 1]. A 0 or a negative value gives a negative index, which Python reads from the end of the list without an error.Testing the index instead of the value: the closing scan reads
nums[i] != i + 1, notnums[i] != i. A filled home holdsi + 1, the value that belongs there, not the bare indexi, so comparing againstialone would call every filled home missing.Forgetting
n + 1: when every home holds its value, as in[2, 1], the answer isn + 1 = 3, which no index names.
4-Phase Thought Process Model
You will see how a senior engineer hears "smallest missing positive, O(1) extra memory" and uses the array as its own hash table.
Pattern Recognition Signals
The 10-second spot
"The smallest positive whole number (1, 2, 3, ...) that does not appear anywhere in nums", "O(n) time" and "only O(1) extra memory beyond the input array": a missing number, with no room for a hash set, and "changing the values inside nums is allowed". Only 1 to n + 1 can be the answer, and each of 1 to n names an index, so the signal is Cyclic Sort: index v - 1 is the home of v.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
An index j that holds j + 1 keeps it, and every swap sends one more value v from 1 to n to its home v - 1; when the swaps end, the first i with nums[i] != i + 1 gives the answer i + 1, or n + 1 if there is none.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Loop on the home,
nums[nums[i] - 1] != nums[i], not onnums[i] != i + 1: in[2,3,2,1]the 2 at index 0 finds its home, index 1, already holding a 2, and the index test would swap the two 2s forever.Save
home = nums[i] - 1before swapping:nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]writesnums[i]first, then computes the second index from the new value.Check
1 <= nums[i] <= nbefore readingnums[nums[i] - 1]: a 0 or a negative value gives a negative index, which Python reads from the end of the list without an error, and a value abovenis past the end.Return
n + 1after the scan: whennumsholds every number from 1 ton, as in[2,1], no index is missing its value and the answer is 3.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Cyclic Sort and let the array be its own hash table. The answer has to be between 1 and n plus 1, because n values can cover at most the numbers 1 to n, so every other value can be ignored. Every value v from 1 to n has a home, index v minus 1. I walk the array, and while the current value has a home that doesn't hold it yet, I swap it there. Each swap sends one value home for good, so there are at most n swaps in total. Then I scan: the first index i whose value isn't i plus 1 gives the answer i plus 1, and if every home is filled it's n plus 1. The trap is the loop test: I check whether the home already holds v, not whether index i holds i plus 1, or a repeated value would swap forever. That's
O(N)time andO(1)extra space.
So: the answer is in 1..n + 1, each v in 1..n has the home v - 1, swap until every value is home or has none, then scan.
Complexity & Mathematical Proof
O(N)
The outer for i in range(n) runs N times. The inner while looks slow, but each pass of its body is one swap that sends a value v to index v - 1, which holds v from then on, and an index that holds its own value is never swapped again: the while test fails there. So at most N swaps happen in the whole run, not per i, and the loops together make at most 2N tests of the while condition. The second for reads each index at most once and stops at the first gap: O(N). Total: O(N).
O(1)
The swaps rearrange nums in place, and the code keeps only n, i and home: O(1) extra space, with no recursion. The answer is one integer.
T(N) = N (outer loop) + at most N swaps in all + N (scan) = O(N)
The outer for i in range(n) runs N times. The inner while looks slow, but each pass of its body is one swap that sends a value v to index v - 1, which holds v from then on, and an index that holds its own value is never swapped again: the while test fails there. So at most N swaps happen in the whole run, not per i, and the loops together make at most 2N tests of the while condition. The second for reads each index at most once and stops at the first gap: O(N). Total: O(N).
Derivation Progression
O(N)
for i in range(n) visits each index once; the while test runs once more than the swaps made at that i.
at most N
Each swap sends one value to its home v - 1 for good, and a value at home is never moved again, so the swaps across every i add up to at most N.
O(N)
The second for reads each index at most once and returns at the first i with nums[i] != i + 1.
O(N)
O(N) loop steps, at most N swaps and one scan.
Variable Definitions
Number of values, len(nums) (at most 10^5)
Memory Architecture & Bounds
O(1): no recursion
O(1): n, i, home
O(1): one integer
Boundary Best / Worst Cases
: no value has a home, as in [7,8,9,11,12], so no swap happens, but every index is still visited once
: a shuffled 1..N, where every value is swapped home once and the scan reads every index
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the smallest positive whole number", **"does not appear anywhere in nums"**, "only O(1) extra memory beyond the input array". A missing number among 1 to n with no room for a set: Cyclic Sort, each value v sent to index v - 1.
Up to values from to . A hash set of the values takes extra memory and sorting takes time, both outside the stated bounds; Cyclic Sort makes at most swaps in all, then one scan.
The input array is the scratch space: a caller that still needs the original order must pass a copy, which brings back the memory the method avoids, so document the mutation. With values from to , compute nums[i] - 1 only after checking 1 <= nums[i] <= n: in C or Java an unchecked index reads outside the array. The swaps jump to scattered positions, so on arrays much larger than the CPU cache each swap can be a cache miss, where a sequential scan is not.
Core Algorithmic State Invariants
A value `v` from 1 to `n` belongs at index `v - 1`. Zeros, negatives and values above `n` have no home and can stay anywhere, because the answer is between 1 and `n + 1`.
Swap while `nums[nums[i] - 1] != nums[i]`. With a repeated value the home already holds a copy, so testing `nums[i] != i + 1` would swap two equal values forever.
Each swap sends one value home for good, so the `while` makes at most `n` swaps in the whole run: O(N) time, and the array itself is the table, O(1) extra space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| The answer lies between 1 and n + 1 | n = len(nums) | `n` values fill at most the numbers 1 to `n`, so the answer is between 1 and `n + 1`, and only values from 1 to `n` need a home. |
| Send the value home while it has one it does not fill yet (the trap: test the home) | while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: | The range test comes first so `nums[i] - 1` is a real index; the home test stops at a repeated value, whose home already holds a copy. |
| Fix the home index before the swap | home = nums[i] - 1 | The swap changes `nums[i]`; saving the home first keeps both targets of the swap pointing at the right places. |
| One swap: one value home for good | nums[i], nums[home] = nums[home], nums[i] | `v` lands at `v - 1` and is never moved again; the value that was there comes to `i` and is tested next. |
| The first index without its value is the answer | if nums[i] != i + 1:
return i + 1 | Every value from 1 to `n` that is present sits at its home, so the first index that fails names the smallest missing number. |
| Every home filled | return n + 1 | All of 1 to `n` are present, so the next number, `n + 1`, is the smallest one missing. |