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)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview