41. First Missing Positive
Asked at Netflix, Oracle, Walmart
Difficulty
Hard
Time
O(n)
Space
O(1)
Pattern
Array
Companies
3
Problem
You are given an unsorted array of integers nums. Return the smallest positive integer (1, 2, 3, ...) that does not appear anywhere in the array.
Zero and negative numbers never count as answers, because the answer must be positive. The array can contain duplicates, big numbers, and negative numbers — all of that is allowed.
The tricky part is the required cost: your algorithm must run in O(n) time and use O(1) extra space. That means no hash set and no sorting, because both would break one of those limits.
Find the first positive number that is absent
Constraints
- ●
1 <= nums.length <= 10^5 - ●
-2^31 <= nums[i] <= 2^31 - 1
Examples
nums = [1,2,0]3nums = [3,4,-1,1]2nums = [7,8,9,11,12]1Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Netflix | Hard | View all Netflix questions → |
| Oracle | Hard | View all Oracle questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
Brute force: for each number from 1 upward, check if it exists in the array using a hash set. Return the first one not found. Time: O(n^2), space: O(n).
Better: use a hash set to store all numbers. Then iterate from 1 upward and return the first number not in the set. Time: O(n), space: O(n). But the problem requires O(1) space.
Sorting approach: sort the array, then scan for the first gap. Time: O(n log n), space: O(1) (in-place sort). But the problem requires O(n) time.
Cyclic sort (optimal): the key insight is that the answer must be in the range [1, n+1] where n is the array length. Place each number in its "correct" position: number i should be at index i-1. Iterate through the array and swap each number to its correct position if it is in [1, n] and not already in place. Then scan for the first position where the value doesn't match.
Time: O(n) — each element is swapped at most once. Space: O(1) — in-place swaps only. This is the optimal solution.
Optimal Approach
Cyclic sort:
- For each index i from 0 to n-1:
- While
nums[i]is in [1, n] andnums[i] != nums[nums[i] - 1]: swapnums[i]withnums[nums[i] - 1].
- While
- Scan the array: find the first index i where
nums[i] != i + 1. Returni + 1. - If all positions are correct, return
n + 1.
Walkthrough: [3, 4, -1, 1]
i=0: nums[0]=3, swap with nums[2]:[-1, 4, 3, 1]. nums[0]=-1, skip.i=1: nums[1]=4, swap with nums[3]:[-1, 1, 3, 4]. nums[1]=1, swap with nums[0]:[1, -1, 3, 4]. nums[1]=-1, skip.i=2: nums[2]=3, correct. Skip.i=3: nums[3]=4, correct. Skip.- Scan: nums[0]=1 (ok), nums[1]=-1 (should be 2). Return 2.
Time: O(n). Space: O(1).
Cyclic sort: send every value home
What Trips People Up in Real Interviews
Using a hash set when the problem requires O(1) space. The hash set approach is O(n) space. Always mention it as an alternative, then optimize to cyclic sort.
The swap condition must check three things: (1) nums[i] is in [1, n], (2) nums[i] is not already in its correct position. Missing any condition causes an infinite loop or incorrect result.
Confusing the index-value relationship. Number i should be at index i-1 (0-indexed). So the correct position for value v is index v-1. Many candidates use index v, which is off by one.
Not using a while loop for the swap. A single if-then-swap is not enough because after swapping, the new value at position i might also need to be swapped. The while loop continues until the current position is correct or the value is out of range.
Forgetting to handle the case where all positions are correct. After the scan, if every nums[i] == i + 1, the answer is n + 1. This happens when the array is a permutation of [1, n].
Solution Code
O(n) timedef firstMissingPositive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1Frequently Asked Questions
What is the First Missing Positive problem?
Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in `O(n)` time and uses `O(1)` extra space.
How do you solve First Missing Positive?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask First Missing Positive?
First Missing Positive is asked at Netflix, Oracle, Walmart. It is a hard difficulty problem.
What are common mistakes on First Missing Positive?
- Using a `hash set` when the problem requires `O(1)` space. The `hash set` approach is `O(n)` space. Always mention it as an alternative, then optimize to cyclic sort.
- The swap condition must check three things: (1) `nums[i]` is in [1, n], (2) `nums[i]` is not already in its correct position. Missing any condition causes an infinite loop or incorrect result.
- Confusing the index-value relationship. Number i should be at index i-1 (0-indexed). So the correct position for value v is index v-1. Many candidates use index v, which is off by one.
- Not using a while loop for the swap. A single if-then-swap is not enough because after swapping, the new value at position i might also need to be swapped. The while loop continues until the current position is correct or the value is out of range.
- Forgetting to handle the case where all positions are correct. After the scan, if every `nums[i] == i + 1`, the answer is `n + 1`. This happens when the array is a permutation of [1, n].