HardArrays
First Missing Positive
googleamazonmicrosoftmetaappleuberoracle
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) auxiliary space.
Example 1:
Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all present, so the smallest missing positive is 3.
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is present but 2 is missing, so the answer is 2.
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
Examples
Example 1
Input: nums = [1,2,0]
Output: 3
Explanation: 1 and 2 are present. The smallest missing positive is 3.
Example 2
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is present but 2 is not, so the answer is 2.
Example 3
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: 1 is not in the array, so it is the smallest missing positive.
Constraints
- -1 <= nums.length <= 10^5
- --2^31 <= nums[i] <= 2^31 - 1
Optimal Complexity
Time
O(n)
Space
O(1)
One problem, two ways to prep
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.