Smallest positive integer that is missing
Hard · Target 25 minutes · Arrays and hashing· Type asked at
Jane Street
Two Sigma
Stripe
Given an unsorted array nums of integers, return the smallest positive
integer that does not appear in it.
Your solution must run in O(n) time and use only O(1) extra space. You may modify the array.
Examples
| Input | Output | Why |
|---|---|---|
nums = [3, 4, -1, 1] | 2 | 1 is present, 2 is not. |
nums = [1, 2, 0] | 3 | 1 and 2 are both there. |
nums = [7, 8, 9, 11, 12] | 1 | Nothing small enough to matter. |
Constraints
- 1 ≤ n ≤ 10⁵
- −2³¹ ≤ nums[i] ≤ 2³¹ − 1
- O(n) time, O(1) extra space
Hints
Hint 1
Without the space limit this is one line: put everything in a set and count up from 1. The limit is the whole problem.
Hint 2
With n numbers, the answer cannot be larger than n + 1. So only the values 1 to n matter, and everything else can be ignored.
Hint 3
You need a table indexed 1..n that records "present". You already own an array of length n. Put each value v in slot v − 1.
Where people lose marks
- Guarding the swap with
nums[i] != i + 1instead ofnums[v − 1] != v. On a duplicate the loop never ends. - In Python, writing the swap as
nums[i], nums[nums[i] - 1] = …. The left side is assigned in order, so the second target is computed from the value just written. Take the index into a variable first. - Forgetting that the answer can be n + 1, and returning something inside the array when every slot is correct.
- Assuming the nested loop is O(n²). Each swap places a value at its final position, so the total number of swaps is at most n.
Dry run on [3,4,-1,1]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7nums3041-1213n4
n = 4, so the answer is somewhere in 1..5. Only values 1..4 matter: put each value v in slot v − 1.
-
Step 2 / 7nums-10i413213i0placed3
Slot 0 holds 3, which belongs in slot 2. Swap it home.
-
Step 3 / 7nums-10i413213i0
Slot 0 holds -1, outside 1..4. It cannot be the answer's evidence either way; leave it.
-
Step 4 / 7nums-1011i3243i1placed4
Slot 1 holds 4, which belongs in slot 3. Swap it home.
-
Step 5 / 7nums10-11i3243i1placed1
Slot 1 holds 1, which belongs in slot 0. Swap it home.
-
Step 6 / 7nums10-11i3243i1
Slot 1 holds -1, outside 1..4. It cannot be the answer's evidence either way; leave it.
-
Step 7 / 7nums10-113243answer2
Read left to right: slot 1 should hold 2 and does not. Answer 2.
How to think about it
With a hash set the problem is trivial, and the space limit exists to forbid exactly that. The way through starts with a bound: the answer is at most n + 1. If 1, 2, …, n are all present they fill every slot, and the answer is n + 1; otherwise one of them is missing. So only values between 1 and n carry information. Zeros, negatives and anything larger than n are noise.
That means the "present" table only needs n entries, and the array already has n slots. Use it.
Walk the array, and while the value in slot i is some v between 1 and n
that is not already at home, swap it into slot v − 1. Each swap sends one value home for
good, so there are at most n swaps in total, even though there is a loop inside a loop.
Then read the array: the first slot i that does not hold i + 1 is the
answer. If every slot is right, the answer is n + 1.
The guard on the swap is what makes it terminate. Duplicates would otherwise swap forever (two 2s
trading places in slot 1), so the condition checks that the destination does not already hold
v, not merely that v is out of place.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
# send nums[i] home to slot nums[i] - 1, until it is out of range or already home
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1 # take the index first: see the pitfalls
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1#include <utility>
#include <vector>
using namespace std;
int solve(vector<int> nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
// send nums[i] home to slot nums[i] - 1, until it is out of range or already home
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
swap(nums[i], nums[nums[i] - 1]);
}
for (int i = 0; i < n; i++)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// send nums[i] home to slot nums[i] - 1, until it is out of range or already home
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int j = nums[i] - 1;
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
}
for (int i = 0; i < n; i++)
if (nums[i] != i + 1) return i + 1;
return n + 1;
}
}function firstMissingPositive(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
// send nums[i] home to slot nums[i] - 1, until it is out of range or already home
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
const j = nums[i] - 1;
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
return n + 1;
}fn solve(nums: &[i32]) -> i32 {
let mut a = nums.to_vec();
let n = a.len();
for i in 0..n {
// send a[i] home to slot a[i] - 1, until it is out of range or already home
while a[i] >= 1 && (a[i] as usize) <= n && a[a[i] as usize - 1] != a[i] {
let j = a[i] as usize - 1;
a.swap(i, j);
}
}
for i in 0..n {
if a[i] != i as i32 + 1 {
return i as i32 + 1;
}
}
n as i32 + 1
}import qualified Data.IntSet as S
-- Pure Haskell has no cheap in-place swap, so this keeps the same bound (the answer is at
-- most n + 1) but records presence in a set. The O(1)-space version needs a mutable array
-- in ST; the placement idea is identical.
solve :: [Int] -> Int
solve xs = head [m | m <- [1 .. n + 1], not (S.member m present)]
where
n = length xs
present = S.fromList [x | x <- xs, x >= 1, x <= n]Variants to try
- You may not modify the array. (Then O(1) space is not achievable in general; use a set, or sort a copy.)
- Find the smallest missing positive greater than some m. (Shift the values by m and apply the same idea.)
- Find every missing number in 1..n. (Same placement pass, then collect every slot that is wrong.)
Next problems
Find every value that appears twice
With a set this is a few lines, and the space limit takes the set away. Since every value is between 1 and n, the sign of nums[v − 1] can remember whether you've met v already.
Open the problem → Easy15 minFind every number from 1 to n that is missing
It's the same sign marking you'd use to find duplicates, only this time you read the answer from the slots that never got marked.
Open the problem → Easy10 minAre two words anagrams?
Two words are anagrams when every letter occurs equally often in both. One table of counts, added for one word and taken away for the other.
Open the problem →Write a solution and run it against the real test table.
Keep going
Find every value that appears twice
With a set this is a few lines, and the space limit takes the set away. Since every value is between 1 and n, the sign of nums[v − 1] can remember whether you've met v already.
Open the problem → Easy15 minFind every number from 1 to n that is missing
It's the same sign marking you'd use to find duplicates, only this time you read the answer from the slots that never got marked.
Open the problem → Easy10 minAre two words anagrams?
Two words are anagrams when every letter occurs equally often in both. One table of counts, added for one word and taken away for the other.
Open the problem → Arrays and hashingThe pattern behind it
Trade memory for time: a hash map answers "have I seen this?" in O(1), and most array problems reduce to asking it the right question.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.