First Missing Positive (LeetCode 41)
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
Core Insight
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.
The Math, Step by Step
1. The number the code looks for
Let be the length of nums. The answer is the smallest positive whole number that is not in nums. Call it .
2. Why the answer is always between 1 and
The argument counts values. It is a form of the pigeonhole principle: values can match at most different numbers. Take the numbers . nums has only elements, so it can hold at most of those numbers. So at least one of is missing, and
Every value outside can never decide the answer. That includes zero, negative numbers and values greater than . A value greater than could only matter if all of were present. Then the answer is in any case.
3. The home of each value
Because only the values matter, each of them gets a fixed place in the array. The home of value is index . So value 1 belongs at index 0, and value belongs at index .
Value nums[i] | What the first loop does with it |
|---|---|
| (zero or negative) | leaves it where it is |
| leaves it where it is | |
| , and its home already holds | leaves it where it is |
| , and its home holds another value | swaps it into its home, then looks at the value that arrived at index i |
After the first loop, every value from to that appears in nums sits in its home. So nums[i] == i + 1 exactly when the value is present. The second loop returns the first index where this fails, as . If every home holds its value, all of are present, and the code returns .
4. Why the swaps stop, and the check that handles repeated values
Every swap puts one value into its home. After that, the home holds its own value, so no later swap moves it again. There are homes, so the whole first loop makes at most swaps. The two loops together take time, even though the first loop contains a while.
The condition nums[nums[i] - 1] != nums[i] handles repeated values. Take nums = [1, 1]. At i = 1 the value is 1, and its home, index 0, already holds 1. Without this check the code would swap 1 with 1 forever. With it, the second 1 stays at index 1. The second loop then finds nums[1] = 1, which is not , and returns .
5. Example 2 by hand
nums = [3,4,-1,1], so and the answer is between 1 and 5.
i | Value at nums[i] | home | Array after the swap |
|---|---|---|---|
| 0 | 3 | 2 | [-1, 4, 3, 1] |
| 0 | none | no swap: is not in | |
| 1 | 4 | 3 | [-1, 1, 3, 4] |
| 1 | 1 | 0 | [1, -1, 3, 4] |
| 1 | none | no swap | |
| 2 | 3 | 2 | no swap: index 2 already holds 3 |
| 3 | 4 | 3 | no swap: index 3 already holds 4 |
The picture shows nums after the first loop. Index 0 holds 1, index 2 holds 3 and index 3 holds 4, so each of these values is in its home. Index 1, marked "missing", holds instead of 2. It is the first index where nums[i] != i + 1. So the second loop returns , the expected output.
6. Example 1 by hand
nums = [1,2,0], so . Value 1 is already at index 0, and value 2 is already at index 1. The value 0 is not in . So the first loop makes no swap. The second loop finds nums[0] = 1 and nums[1] = 2 in their homes. At index 2 it finds 0 instead of 3, and it returns , the expected output.
7. From the facts to the code
| Fact | In firstMissingPositive |
|---|---|
| only can decide the answer | 1 <= nums[i] <= n |
| the home of is index | home = nums[i] - 1 |
| stop when the home already holds | nums[nums[i] - 1] != nums[i] |
| index should hold | if nums[i] != i + 1: followed by return i + 1 |
| all of present | return n + 1 |
The array itself stores the homes, so the code uses extra memory, as the problem requires.
| 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. |
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.
🔑 Why It Works
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.
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
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
When the swaps end, every value from 1 to n that appears sits at its home, so 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
while ... nums[nums[i] - 1] != nums[i]: test the home, not the index (gotcha 1 has the input that loops forever).
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.
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)
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
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 works inside nums with one pass of swaps and 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 Short Trace:
[3, 4, -1, 1]
At i = 0 the 3 goes to index 2: [-1, 4, 3, 1], and -1 has no home. At i = 1 the 4 goes to index 3: [-1, 1, 3, 4]; the 1 that arrives also has a home, index 0: [1, -1, 3, 4]. Indexes 2 and 3 already hold their values. The scan finds index 1 without a 2, so the answer is 2.
First Missing Positive (LeetCode 41)
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
Core Insight
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.
The Math, Step by Step
1. The number the code looks for
Let be the length of nums. The answer is the smallest positive whole number that is not in nums. Call it .
2. Why the answer is always between 1 and
The argument counts values. It is a form of the pigeonhole principle: values can match at most different numbers. Take the numbers . nums has only elements, so it can hold at most of those numbers. So at least one of is missing, and
Every value outside can never decide the answer. That includes zero, negative numbers and values greater than . A value greater than could only matter if all of were present. Then the answer is in any case.
3. The home of each value
Because only the values matter, each of them gets a fixed place in the array. The home of value is index . So value 1 belongs at index 0, and value belongs at index .
Value nums[i] | What the first loop does with it |
|---|---|
| (zero or negative) | leaves it where it is |
| leaves it where it is | |
| , and its home already holds | leaves it where it is |
| , and its home holds another value | swaps it into its home, then looks at the value that arrived at index i |
After the first loop, every value from to that appears in nums sits in its home. So nums[i] == i + 1 exactly when the value is present. The second loop returns the first index where this fails, as . If every home holds its value, all of are present, and the code returns .
4. Why the swaps stop, and the check that handles repeated values
Every swap puts one value into its home. After that, the home holds its own value, so no later swap moves it again. There are homes, so the whole first loop makes at most swaps. The two loops together take time, even though the first loop contains a while.
The condition nums[nums[i] - 1] != nums[i] handles repeated values. Take nums = [1, 1]. At i = 1 the value is 1, and its home, index 0, already holds 1. Without this check the code would swap 1 with 1 forever. With it, the second 1 stays at index 1. The second loop then finds nums[1] = 1, which is not , and returns .
5. Example 2 by hand
nums = [3,4,-1,1], so and the answer is between 1 and 5.
i | Value at nums[i] | home | Array after the swap |
|---|---|---|---|
| 0 | 3 | 2 | [-1, 4, 3, 1] |
| 0 | none | no swap: is not in | |
| 1 | 4 | 3 | [-1, 1, 3, 4] |
| 1 | 1 | 0 | [1, -1, 3, 4] |
| 1 | none | no swap | |
| 2 | 3 | 2 | no swap: index 2 already holds 3 |
| 3 | 4 | 3 | no swap: index 3 already holds 4 |
The picture shows nums after the first loop. Index 0 holds 1, index 2 holds 3 and index 3 holds 4, so each of these values is in its home. Index 1, marked "missing", holds instead of 2. It is the first index where nums[i] != i + 1. So the second loop returns , the expected output.
6. Example 1 by hand
nums = [1,2,0], so . Value 1 is already at index 0, and value 2 is already at index 1. The value 0 is not in . So the first loop makes no swap. The second loop finds nums[0] = 1 and nums[1] = 2 in their homes. At index 2 it finds 0 instead of 3, and it returns , the expected output.
7. From the facts to the code
| Fact | In firstMissingPositive |
|---|---|
| only can decide the answer | 1 <= nums[i] <= n |
| the home of is index | home = nums[i] - 1 |
| stop when the home already holds | nums[nums[i] - 1] != nums[i] |
| index should hold | if nums[i] != i + 1: followed by return i + 1 |
| all of present | return n + 1 |
The array itself stores the homes, so the code uses extra memory, as the problem requires.
| 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. |
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.
🔑 Why It Works
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.
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
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
When the swaps end, every value from 1 to n that appears sits at its home, so 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
while ... nums[nums[i] - 1] != nums[i]: test the home, not the index (gotcha 1 has the input that loops forever).
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.
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)
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
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 works inside nums with one pass of swaps and 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 Short Trace:
[3, 4, -1, 1]
At i = 0 the 3 goes to index 2: [-1, 4, 3, 1], and -1 has no home. At i = 1 the 4 goes to index 3: [-1, 1, 3, 4]; the 1 that arrives also has a home, index 0: [1, -1, 3, 4]. Indexes 2 and 3 already hold their values. The scan finds index 1 without a 2, so the answer is 2.