First Missing Positive
HardArray
Description
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.
Examples
Input:
nums = [1,2,0]Output:
3Explanation:
1 and 2 are present, so 3 is the first missing positive.
Input:
nums = [3,4,-1,1]Output:
2Explanation:
1 is present but 2 is missing.
Input:
nums = [7,8,9,11,12]Output:
1Explanation:
All numbers are >= 7, so the smallest positive 1 is absent. Check positives 1,2,3... sequentially.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.