MaiDeveloper

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) {
    contains.add(n);
  }

  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)


Mike Mai
Mike Mai   Brooklyn, New York
I am a full-stack web developer. I love to learn cutting-edge technology and solve problems. I also like photography and graphic designs.