First Missing Positive
Problem
Given an unsorted integer array, return the smallest positive integer that does not appear in it. It must run in O(n) time and O(1) extra space.
Example 1
Input: [1, 2, 0] Output: 3
Example 2
Input: [3, 4, -1, 1] Output: 2
Example 3
Input: [7, 8, 9, 11, 12] Output: 1
Test cases
Case 1
Input: [1,2,0] Expected: 3
Case 2
Input: [3,4,-1,1] Expected: 2
Case 3
Input: [7,8,9,11,12] Expected: 1
View solutionHide solution2 approaches
1. Hash set
Time O(n)Space O(n)
Put everything in a set, then test 1, 2, 3… — simple but O(n) space.
function firstMissingPositive(nums) { const s = new Set(nums); let i = 1; while (s.has(i)) i++; return i;}2. Cyclic sort
Time O(n) — each swap fixes one valueSpace O(1)
The answer is in 1..n+1. Swap each value v in range into index v − 1; the first index i with nums[i] ≠ i + 1 gives the answer.
function firstMissingPositive(nums) { const n = nums.length; for (let i = 0; i < n; i++) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) { const j = nums[i] - 1; [nums[i], nums[j]] = [nums[j], nums[i]]; } } for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1; return n + 1;}