Builds on Read-Write Pointers, which you haven’t finished yet.
Cyclic Sort (Index as Hash, First Missing Positive)
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.
Cyclic Sort
values 1..n ➔ swap each value v to index v - 1 ➔ first index i not holding i + 1O(n) time with O(1) extra memory.| 1 | def first_missing_positive(nums: list[int]) -> int: |
| 2 | """First Missing Positive: send every value v from 1 to n to its home index v - 1, then find the first index that does not hold its own value. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | n = len(nums) |
| 6 | # 1. Send Every Value Home: |
| 7 | # Value v belongs at index v - 1, so swap while nums[i] is in range 1..n and its home does not hold it yet; each swap sends one more value home for good, so the loop ends after at most n swaps. |
| 8 | for i in range(n): |
| 9 | while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: |
| 10 | home = nums[i] - 1 # Save the home before the swap changes nums[i] |
| 11 | nums[i], nums[home] = nums[home], nums[i] # v goes home for good; the value from there comes to i |
| 12 | # 2. Find The First Empty Home: |
| 13 | # An index i whose value is not i + 1 is the first home still missing its value, so i + 1 is the answer. |
| 14 | for i in range(n): |
| 15 | if nums[i] != i + 1: |
| 16 | return i + 1 |
| 17 | return n + 1 # Every home from 1 to n is filled |
j that holds j + 1 keeps it for the rest of the run, and every swap sends one more value v from 1 to n to its home v - 1.Each value v from 1 to n has a home, index v - 1, so the array can be its own hash table: swap every value into its home, and afterwards the first index i with nums[i] != i + 1 gives the missing number i + 1, or n + 1 if every home is filled. This is enough because n values fill at most n homes, so the answer is always between 1 and n + 1, and zeros, negatives and values above n can stay wherever they end up; each swap sends one value home for good, and a value at home is never moved again, so there are at most n swaps in all. The trap is the while test: swap while nums[nums[i] - 1] != nums[i] (the home does not hold v yet), not while nums[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.
See it run
Index Home, step by step
i -nums[i] -home -swaps 0
Each cell holds one value of nums. Phase 1 swaps values to their homes. Phase 2 scans for the first index that does not hold index + 1.
ithe index the loop is working onhomethe index v - 1 where the value belongsstopthe value at index i stays, because it is at home, a repeat, or out of rangegapthe first index whose value is not index + 1
Start: nums = [3, 4, -1, 1, 3] and n = 5. A value v from 1 to 5 belongs at index v - 1.
Gotcha 1 of 4
- The trap
Gotcha 1: Testing
nums[i] != i + 1in the swap loopMistakewhile 1 <= nums[i] <= n and nums[i] != i + 1:Fixwhile 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:What happens: The loop should stop when the home of
nums[i]already holds that value.nums[i] != i + 1asks about indexiinstead. With a repeated value, both copies have the same home. The swap exchanges two equal values, nothing changes, and the loop never ends.Example: nums = [1, 1]Mistake: the loop never endsFix: returns 2
- The array must not be changed, as in Find the Duplicate Number (LC 287): no swap is allowed, so the values are followed as links from index to index instead of being sent home. See Fast & Slow Pointers
- The values are any integers, not the numbers 1 to n, as in Single Number (LC 136): a value names no index, so there is no home to send it to. See XOR Cancel
- The values say nothing about positions, as in Set Matrix Zeroes (LC 73): the marks must go into cells whose final value is already known, not to an index a value names. See In-Place Marking
Deep Dive
The answer is small, so the array can be its own hash table
For an array of length n, the first missing positive number is always between 1 and n + 1. The array has only n slots, so it can hold at most n different positive values. If 1 to n are all present, the answer is n + 1. Otherwise some value from 1 to n is missing, and the answer is the smallest one.
So values below 1 and above n do not matter. They can stay anywhere.
The extra idea of this card, added to Read and Write, is to write the value 1 to n at a fixed place. The home of value v is index v - 1. After every value is at its home, index i holds i + 1 when i + 1 is present, and holds something else when it is missing.
The array then records which values are present. This is a hash table where the hash function is v - 1, so it needs no extra memory.
Traced on [3, 4, -1, 1, 3]
Here n = 5, so the homes are indexes 0 to 4 for the values 1 to 5. The loop works on index i until nums[i] cannot move.
i = 0: nums[0] = 3 belongs at index 2, which holds -1. The swap gives [-1, 4, 3, 1, 3]. Now nums[0] = -1 has no home, so the loop moves on.
i = 1: 4 belongs at index 3, which holds 1. After the swap, the array is [-1, 1, 3, 4, 3]. Now nums[1] = 1 belongs at index 0, which holds -1. After the second swap the array is [1, -1, 3, 4, 3], and nums[1] = -1 has no home.
i = 2 and i = 3 already hold 3 and 4 at their homes. At i = 4, the value 3 belongs at index 2, and index 2 already holds 3. This is a repeat, so the loop moves on. There were 3 swaps.
The scan finds nums[0] = 1, then nums[1] = -1, which is not 2. The answer is 2. On the LeetCode example [3, 4, -1, 1] the same code returns 2, and on [7, 8, 9, 11, 12] it returns 1.
The while test, and why the run is O(N)
The loop condition is 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]. It says: the value has a home, and the home does not already hold this value.
The shorter test nums[i] != i + 1 looks similar but is wrong. With a repeat, both copies have the same home. For [1, 1], index 1 holds 1, and 1 != 2, so the loop swaps index 1 with index 0. Both hold 1, nothing changes, and the loop never ends.
Each swap puts one value at its home for good, because a value at home satisfies nums[home] == v and is never moved again. There are at most n homes, so there are at most n swaps in the whole run. The for loop adds n more steps, and the time is O(N). The space is O(1), because the array is changed in place.
The range test must come first. A value above n has no home, and nums[nums[i] - 1] would read past the end of the list. [7, 8, 9, 11, 12] raises an IndexError without the range test.
Writing the swap, and the final scan
The blueprint saves home = nums[i] - 1 before the swap. After the swap, nums[i] holds a different value. In the one-line form nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i], Python assigns the targets from left to right. The first target changes nums[i], and the second target is then computed from the new value, so the old value lands in the wrong place.
The final scan compares nums[i] with i + 1, not with i. A filled home at index 0 holds 1. Testing nums[i] != i calls every filled home missing, and [1, 2, 0] would return 1 instead of 3.
If the scan finds no mismatch, every value from 1 to n is present, and the answer is n + 1.
The same idea finds repeated values too. After the swaps, an index i that does not hold i + 1 holds either a value with no home or a repeat of a value that is already at home.
60-Second Pitch
"The answer is between 1 and n + 1, so values outside 1 to n do not matter. I use the array as its own hash table. The home of value v is index v - 1. For each index I swap while the value is in range and its home does not hold it yet. Each swap sends one value home for good, so there are at most n swaps and the time is O(N). The test looks at the home, not at i + 1, so repeated values cannot loop forever. Then I scan for the first index i where nums[i] is not i + 1. The answer is i + 1, or n + 1 if none. The space is O(1)."
Common Questions
- Why is the answer always between 1 and n + 1?
The array has
nslots, so it holds at mostndifferent positive values. If it holds all of 1 ton, the answer isn + 1. If not, some value from 1 tonis missing, and the smallest missing value is at mostn.- Why is the nested loop
O(N)and not O(N^2)? Every swap sends one value to its home, and a value at home is never moved again. There are at most
nhomes, so thewhileloop swaps at mostntimes in total across all values ofi.- Why does the while test look at nums[nums[i] - 1]?
The swap is useful only if the home does not already hold the value. A repeat has a home that already holds a copy. Swapping two equal values changes nothing, so the loop would never end. The test on the home stops it.
- Can you use a set instead?
Yes. Put all values in a set and test 1, 2, 3 and so on until one is missing. It is simple, but it uses
O(N)extra space. This card exists for theO(1)space requirement.- How does the same idea find a repeated number?
Run the swaps. Then an index
iwithnums[i] != i + 1holds a value that is out of range or a repeat of a value that is already at its home. The repeated values are found among those entries, as in Find All Duplicates in an Array (LC 442).
SWE Reasoning
Spot it
- The array has length
n, and the values of interest are the numbers 1 ton. - The question asks which number is missing or repeated (First Missing Positive (LC 41)).
- The task requires
O(n)time andO(1)extra memory, so a set or a count table is not allowed. - Values outside 1 to
ncan be ignored, because the answer is at mostn + 1.
The invariant, step by step
- The home of value
vis indexv - 1. - For each
i, whilenums[i]is in 1 tonand its home does not hold it yet, savehome = nums[i] - 1and swapnums[i]withnums[home]. - After a swap, the value is at its home for good. It is never moved again, so there are at most
nswaps. - The loop stops at an index when its value has no home, is already at home, or repeats a value that is at its home.
- In the scan, the first index
iwithnums[i] != i + 1meansi + 1is missing, andi + 1is the answer. - If there is no such index, the answer is
n + 1.
Traps
while ... nums[i] != i + 1. With a repeat, such as[1, 1], the swap changes nothing and the loop never ends.- A one-line swap with
nums[nums[i] - 1]. The second target is computed from the newnums[i], so the swaps make no progress. - No range test first.
[7, 8, 9, 11, 12]raises anIndexError. - Scan with
nums[i] != i. Every filled home is called missing, and[1, 2, 0]returns 1.
Practice
Builds on Read-Write Pointers, which you haven’t finished yet.
Cyclic Sort (Index as Hash, First Missing Positive)
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.
Cyclic Sort
values 1..n ➔ swap each value v to index v - 1 ➔ first index i not holding i + 1O(n) time with O(1) extra memory.| 1 | def first_missing_positive(nums: list[int]) -> int: |
| 2 | """First Missing Positive: send every value v from 1 to n to its home index v - 1, then find the first index that does not hold its own value. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | n = len(nums) |
| 6 | # 1. Send Every Value Home: |
| 7 | # Value v belongs at index v - 1, so swap while nums[i] is in range 1..n and its home does not hold it yet; each swap sends one more value home for good, so the loop ends after at most n swaps. |
| 8 | for i in range(n): |
| 9 | while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: |
| 10 | home = nums[i] - 1 # Save the home before the swap changes nums[i] |
| 11 | nums[i], nums[home] = nums[home], nums[i] # v goes home for good; the value from there comes to i |
| 12 | # 2. Find The First Empty Home: |
| 13 | # An index i whose value is not i + 1 is the first home still missing its value, so i + 1 is the answer. |
| 14 | for i in range(n): |
| 15 | if nums[i] != i + 1: |
| 16 | return i + 1 |
| 17 | return n + 1 # Every home from 1 to n is filled |
j that holds j + 1 keeps it for the rest of the run, and every swap sends one more value v from 1 to n to its home v - 1.Each value v from 1 to n has a home, index v - 1, so the array can be its own hash table: swap every value into its home, and afterwards the first index i with nums[i] != i + 1 gives the missing number i + 1, or n + 1 if every home is filled. This is enough because n values fill at most n homes, so the answer is always between 1 and n + 1, and zeros, negatives and values above n can stay wherever they end up; each swap sends one value home for good, and a value at home is never moved again, so there are at most n swaps in all. The trap is the while test: swap while nums[nums[i] - 1] != nums[i] (the home does not hold v yet), not while nums[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.
See it run
Index Home, step by step
i -nums[i] -home -swaps 0
Each cell holds one value of nums. Phase 1 swaps values to their homes. Phase 2 scans for the first index that does not hold index + 1.
ithe index the loop is working onhomethe index v - 1 where the value belongsstopthe value at index i stays, because it is at home, a repeat, or out of rangegapthe first index whose value is not index + 1
Start: nums = [3, 4, -1, 1, 3] and n = 5. A value v from 1 to 5 belongs at index v - 1.
Gotcha 1 of 4
- The trap
Gotcha 1: Testing
nums[i] != i + 1in the swap loopMistakewhile 1 <= nums[i] <= n and nums[i] != i + 1:Fixwhile 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:What happens: The loop should stop when the home of
nums[i]already holds that value.nums[i] != i + 1asks about indexiinstead. With a repeated value, both copies have the same home. The swap exchanges two equal values, nothing changes, and the loop never ends.Example: nums = [1, 1]Mistake: the loop never endsFix: returns 2
- The array must not be changed, as in Find the Duplicate Number (LC 287): no swap is allowed, so the values are followed as links from index to index instead of being sent home. See Fast & Slow Pointers
- The values are any integers, not the numbers 1 to n, as in Single Number (LC 136): a value names no index, so there is no home to send it to. See XOR Cancel
- The values say nothing about positions, as in Set Matrix Zeroes (LC 73): the marks must go into cells whose final value is already known, not to an index a value names. See In-Place Marking
Deep Dive
The answer is small, so the array can be its own hash table
For an array of length n, the first missing positive number is always between 1 and n + 1. The array has only n slots, so it can hold at most n different positive values. If 1 to n are all present, the answer is n + 1. Otherwise some value from 1 to n is missing, and the answer is the smallest one.
So values below 1 and above n do not matter. They can stay anywhere.
The extra idea of this card, added to Read and Write, is to write the value 1 to n at a fixed place. The home of value v is index v - 1. After every value is at its home, index i holds i + 1 when i + 1 is present, and holds something else when it is missing.
The array then records which values are present. This is a hash table where the hash function is v - 1, so it needs no extra memory.
Traced on [3, 4, -1, 1, 3]
Here n = 5, so the homes are indexes 0 to 4 for the values 1 to 5. The loop works on index i until nums[i] cannot move.
i = 0: nums[0] = 3 belongs at index 2, which holds -1. The swap gives [-1, 4, 3, 1, 3]. Now nums[0] = -1 has no home, so the loop moves on.
i = 1: 4 belongs at index 3, which holds 1. After the swap, the array is [-1, 1, 3, 4, 3]. Now nums[1] = 1 belongs at index 0, which holds -1. After the second swap the array is [1, -1, 3, 4, 3], and nums[1] = -1 has no home.
i = 2 and i = 3 already hold 3 and 4 at their homes. At i = 4, the value 3 belongs at index 2, and index 2 already holds 3. This is a repeat, so the loop moves on. There were 3 swaps.
The scan finds nums[0] = 1, then nums[1] = -1, which is not 2. The answer is 2. On the LeetCode example [3, 4, -1, 1] the same code returns 2, and on [7, 8, 9, 11, 12] it returns 1.
The while test, and why the run is O(N)
The loop condition is 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]. It says: the value has a home, and the home does not already hold this value.
The shorter test nums[i] != i + 1 looks similar but is wrong. With a repeat, both copies have the same home. For [1, 1], index 1 holds 1, and 1 != 2, so the loop swaps index 1 with index 0. Both hold 1, nothing changes, and the loop never ends.
Each swap puts one value at its home for good, because a value at home satisfies nums[home] == v and is never moved again. There are at most n homes, so there are at most n swaps in the whole run. The for loop adds n more steps, and the time is O(N). The space is O(1), because the array is changed in place.
The range test must come first. A value above n has no home, and nums[nums[i] - 1] would read past the end of the list. [7, 8, 9, 11, 12] raises an IndexError without the range test.
Writing the swap, and the final scan
The blueprint saves home = nums[i] - 1 before the swap. After the swap, nums[i] holds a different value. In the one-line form nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i], Python assigns the targets from left to right. The first target changes nums[i], and the second target is then computed from the new value, so the old value lands in the wrong place.
The final scan compares nums[i] with i + 1, not with i. A filled home at index 0 holds 1. Testing nums[i] != i calls every filled home missing, and [1, 2, 0] would return 1 instead of 3.
If the scan finds no mismatch, every value from 1 to n is present, and the answer is n + 1.
The same idea finds repeated values too. After the swaps, an index i that does not hold i + 1 holds either a value with no home or a repeat of a value that is already at home.
60-Second Pitch
"The answer is between 1 and n + 1, so values outside 1 to n do not matter. I use the array as its own hash table. The home of value v is index v - 1. For each index I swap while the value is in range and its home does not hold it yet. Each swap sends one value home for good, so there are at most n swaps and the time is O(N). The test looks at the home, not at i + 1, so repeated values cannot loop forever. Then I scan for the first index i where nums[i] is not i + 1. The answer is i + 1, or n + 1 if none. The space is O(1)."
Common Questions
- Why is the answer always between 1 and n + 1?
The array has
nslots, so it holds at mostndifferent positive values. If it holds all of 1 ton, the answer isn + 1. If not, some value from 1 tonis missing, and the smallest missing value is at mostn.- Why is the nested loop
O(N)and not O(N^2)? Every swap sends one value to its home, and a value at home is never moved again. There are at most
nhomes, so thewhileloop swaps at mostntimes in total across all values ofi.- Why does the while test look at nums[nums[i] - 1]?
The swap is useful only if the home does not already hold the value. A repeat has a home that already holds a copy. Swapping two equal values changes nothing, so the loop would never end. The test on the home stops it.
- Can you use a set instead?
Yes. Put all values in a set and test 1, 2, 3 and so on until one is missing. It is simple, but it uses
O(N)extra space. This card exists for theO(1)space requirement.- How does the same idea find a repeated number?
Run the swaps. Then an index
iwithnums[i] != i + 1holds a value that is out of range or a repeat of a value that is already at its home. The repeated values are found among those entries, as in Find All Duplicates in an Array (LC 442).
SWE Reasoning
Spot it
- The array has length
n, and the values of interest are the numbers 1 ton. - The question asks which number is missing or repeated (First Missing Positive (LC 41)).
- The task requires
O(n)time andO(1)extra memory, so a set or a count table is not allowed. - Values outside 1 to
ncan be ignored, because the answer is at mostn + 1.
The invariant, step by step
- The home of value
vis indexv - 1. - For each
i, whilenums[i]is in 1 tonand its home does not hold it yet, savehome = nums[i] - 1and swapnums[i]withnums[home]. - After a swap, the value is at its home for good. It is never moved again, so there are at most
nswaps. - The loop stops at an index when its value has no home, is already at home, or repeats a value that is at its home.
- In the scan, the first index
iwithnums[i] != i + 1meansi + 1is missing, andi + 1is the answer. - If there is no such index, the answer is
n + 1.
Traps
while ... nums[i] != i + 1. With a repeat, such as[1, 1], the swap changes nothing and the loop never ends.- A one-line swap with
nums[nums[i] - 1]. The second target is computed from the newnums[i], so the swaps make no progress. - No range test first.
[7, 8, 9, 11, 12]raises anIndexError. - Scan with
nums[i] != i. Every filled home is called missing, and[1, 2, 0]returns 1.