Hard
First Missing Positive
- Time limit
- 3 s
- Memory limit
- 256 MB
- Estimated
- 20 min
- Array Techniques
Description
Description
Given an unsorted integer array nums, return the smallest positive integer that does not appear in nums. Your algorithm should run in O(n) time using O(1) extra space beyond the input (a local working copy is fine).
Examples
Example 1
- Input:
nums = [1, 2, 0] - Output:
3
Example 2
- Input:
nums = [3, 4, -1, 1] - Output:
2
Example 3
- Input:
nums = [7, 8, 9, 11, 12] - Output:
1
Expected Function Behavior
Implement firstMissingPositive(nums) and return the smallest missing positive integer.
Constraints
0 <= nums.length <= 100000-1000000000 <= nums[i] <= 1000000000
Sample cases
3Sample 1
Input
nums = [1,2,0]
Expected output
3
Sample 2
Input
nums = [3,4,-1,1]
Expected output
2
Skills and languages
Patterns
- Cyclic Sort and Index as Hash
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer