May 24, 2019

First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

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
``````

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solution

``````/**
* First Missing Positive
* @param {number[]} nums
* @return {number}
* @time complexity: O(n)
* @space complexity: O(1)
*/
function firstMissingPositive(nums) {
const contains = new Set();
let num = 1;

for (let n of nums) {
}

while (true) {
if (!contains.has(num)) {
return num;
}
num++;
}
}
``````

Alternative Solution

``````/**
* First Missing Positive
* @param {number[]} nums
* @return {number}
* @time complexity: O(n)
* @space complexity: O(1)
*/
function firstMissingPositiveUsingSort(nums) {
let num = 1;

nums.sort((a, b) => a - b);

for (let n of nums) {
if (n === num) {
num++;
} else if (n > num) {
return num;
}
}

return num;
}
``````

Test Case

``````const assert = require('chai').assert;

describe('First Missing Positive', () => {

it('should return 3 when [1,2,0] is given', () => {
assert.strictEqual(firstMissingPositive([1,2,0]), 3);
});

it('should return 2 when [3,4,-1,1] is given', () => {
assert.strictEqual(firstMissingPositive([3,4,-1,1]), 2);
});

it('should return 1 when [7,8,9,11,12] is given', () => {
assert.strictEqual(firstMissingPositive([7,8,9,11,12]), 1);
});

});
``````
``````  First Missing Positive
✓ should return 3 when [1,2,0] is given
✓ should return 2 when [3,4,-1,1] is given
✓ should return 1 when [7,8,9,11,12] is given

3 passing (12ms)
``````