First Missing Positive

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}