Leetcode•Jun 11, 2025
First Missing Positive
Hazrat Ali
Leetcode
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 in the array.
Example 2:
Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing.
Example 3:
Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest positive integer 1 is missing.
Solution
/**
* @param {number[]} A
* @return {number}
*/
const firstMissingPositive = A => {
const n = A.length;
let i = 0;
while (i < n) {
if (A[i] > 0 && A[i] <= n && A[i] !== A[A[i] - 1]) swap(A, i, A[i] - 1);
else i++;
}
i = 0;
while (i < n && A[i] === i + 1) {
i++;
}
return i + 1;
};
const swap = (A, i, j) => ([A[i], A[j]] = [A[j], A[i]]);