DEV Community

loading...

First Missing Positive

jpantunes profile image JP Antunes ・1 min read

Given an unsorted integer array, find the smallest missing positive integer. Note: Your algorithm should run in O(n) time and use constant extra space.

Sounds hard right?

var firstMissingPositive = function(nums) {
  if (nums.length <= 1)  return nums[0] == 1 ? 2 : 1;    

  const max = Math.max(...nums);
  for (let i = 1; i <= max + 1; i++) {
      if (!nums.includes(i)) return i;
      //alternatively: if (nums.indexOf(i) === -1) return i;
  }    
  return 1; //every other case, ie all n in nums are < 0
};

// Runtime: 48 ms, faster than 95.76% of JavaScript online submissions for First Missing Positive.
// Memory Usage: 33.8 MB, less than 91.67% of JavaScript online submissions for First Missing Positive.

Discussion

pic
Editor guide