HardArraysAI interview only
First Missing Positive
Asked atgoogleamazonmicrosoftmetaappleuberoracle
01 · 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) auxiliary space.
02 · Examples
Example 01
Input
nums = [1,2,0]
Output
3
1 and 2 are present. The smallest missing positive is 3.
Example 02
Input
nums = [3,4,-1,1]
Output
2
1 is present but 2 is not, so the answer is 2.
Example 03
Input
nums = [7,8,9,11,12]
Output
1
1 is not in the array, so it is the smallest missing positive.
03 · Constraints
- 011 <= nums.length <= 105
- 02-231 <= nums[i] <= 231 - 1
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.