#41 First Missing Positive
frequently reported atNetflixTCSAmazonMicrosoftGoogleBloomberg
the problem
In plain words
Given an unsorted integer array, return the smallest positive integer (1, 2, 3, …) that does not appear in it. Your solution must run in O(n) time and use O(1) extra memory.
in nums = [1,2,0]
out 3
1 and 2 are present.
in nums = [3,4,-1,1]
out 2
1 is present, 2 is missing.
in nums = [7,8,9,11,12]
out 1
Even 1 is missing.
- 1 ≤ n ≤ 10⁵
- -2³¹ ≤ nums[i] ≤ 2³¹ − 1
- O(n) time, O(1) extra space
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternIn-place markersHash lookup (seen before?)
With n numbers, the answer is somewhere in 1..n + 1. So only values 1..n matter — and each one has a natural home: index v − 1. Put every value in its home; the first index that doesn't hold its owner names the answer.
solutions
From brute force to optimal
For each candidate starting at 1, scan the whole array for it.
- candidate = 1.
- Scan the array for candidate; if it's missing, return it.
- Otherwise try candidate + 1.
Up to n + 1 candidates, each needing a full scan: 10¹⁰ steps at n = 10⁵.
A candidate and a flag.
class Solution { public int firstMissingPositive(int[] nums) { for (int candidate = 1; ; candidate++) { // the answer is at most n + 1 boolean found = false; for (int x : nums) { if (x == candidate) { found = true; break; } } if (!found) return candidate; // a full scan per candidate: O(n²) } }}Put every value in a set, then count up from 1 until a value is missing.
- Add all values to a HashSet.
- candidate = 1; while the set contains it, candidate++.
- Return candidate.
n adds and at most n + 1 lookups, O(1) each on average.
The set holds up to n values — this breaks the O(1) memory rule.
class Solution { public int firstMissingPositive(int[] nums) { Set<Integer> present = new HashSet<>(); for (int x : nums) present.add(x); int candidate = 1; while (present.contains(candidate)) candidate++; // at most n + 1 checks return candidate; }}Use the array itself as the set: swap every value in 1..n into its home slot, then look for the first slot without its owner.
- For each i: while nums[i] is in 1..n and its home nums[nums[i] − 1] doesn't already hold it, swap it home.
- Scan again: the first i with nums[i] ≠ i + 1 → return i + 1.
- Every slot holds its owner → return n + 1.
Each swap puts one value in its home for good, so the whole run makes at most n swaps — the inner while is not O(n) per i.
Swaps happen inside the input array.
class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { // Value v belongs at index v - 1. Keep sending nums[i] home while it has a home in 1..n // and that home doesn't already hold v (a duplicate would swap forever). while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { int home = nums[i] - 1; int tmp = nums[home]; nums[home] = nums[i]; nums[i] = tmp; } } for (int i = 0; i < n; i++) { if (nums[i] != i + 1) return i + 1; // first slot without its owner } return n + 1; // 1..n are all present }}Dry run
Same homes, different marker: a negative number at index v − 1 means "v was seen".
- Replace every value outside 1..n with n + 1 (it can't be the answer).
- For each v = |nums[i]| ≤ n: make nums[v − 1] negative.
- The first positive slot i → return i + 1; none → n + 1.
Three linear passes.
The signs of the input carry the marks.
class Solution { public int firstMissingPositive(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { if (nums[i] <= 0 || nums[i] > n) nums[i] = n + 1; // useless values → a harmless n + 1 } for (int i = 0; i < n; i++) { int v = Math.abs(nums[i]); // the sign may already be flipped if (v <= n && nums[v - 1] > 0) nums[v - 1] = -nums[v - 1]; // negative = "v was seen" } for (int i = 0; i < n; i++) { if (nums[i] > 0) return i + 1; } return n + 1; }}in the room
How to say it in the interview
talk track
- Say the bound first: "n numbers can cover at most 1..n, so the answer is between 1 and n + 1."
- Give the HashSet answer, then: "for O(1) memory I'll use the array itself as the set — index v − 1 records whether v is present."
- Defend the O(n) claim before you're asked: every swap settles one value permanently, so there are at most n swaps in total.
traps
- Leaving out the
nums[nums[i] − 1] != nums[i]check: a duplicate keeps swapping with its twin forever. - Moving i forward right after a swap: the value that just arrived at i still needs to go home.
- Sign marking without first replacing zeros and negatives: 0 can't carry a minus sign, and negatives look like marks.
what they ask next
Follow-ups
Missing Number (LC 268): exactly one of 0..n is missing?
Easier: n(n + 1)/2 minus the actual sum, or XOR everything — see the Bit Manipulation chapter.
Find All Duplicates in an Array (LC 442)?
The same homes idea: values are 1..n, so negate nums[|v| − 1] on each visit; finding that slot already negative means v is a duplicate.
before you submit
Edge cases to test
- [1] → 2 and [2] → 1.
- Duplicates ([1,1] → 2): the home check stops an endless swap.
- Huge or negative values (±2³¹) are skipped — never used as indices.
- A shuffled 1..n → n + 1.
practise next
Similar problems
- #268Missing NumberEasyin Bits
- #128Longest Consecutive SequenceMediumin Hashing