First Missing Positive
Hard · Arrays & Hashing · Array · Hash Table · Cyclic Sort
Problem
You are given an unsorted integer array nums. Return the smallest positive integer that does not appear in nums.
Aim for O(n) time and O(1) extra space: no sorting and no hash set. You may rearrange nums itself.
Examples
Input: nums = [4,1,-6,2] Output: 3
1 and 2 are present; 3 is the first positive integer missing.
Input: nums = [100,0] Output: 1
1 does not appear. Zero and numbers above the length never matter.
Input: nums = [2,3,1] Output: 4
1 through 3 are all present, so the answer is one past the length.
Constraints
- 1 <= len(nums) <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Baseline: sort, then count up from 1 — time O(n log n), space O(n) for the sorted copy
Follow-up
The array is read-only. You can still get O(n) time, but now you need O(n) extra space (a boolean table of size n + 1). Can you show that constant extra space is no longer enough without changing the input?
Related problems
Start free on Cariara · Coding problems · System design studio
