Skip to content

Instantly share code, notes, and snippets.

@d-rat

d-rat/firstMissingIndex

Last active July 12, 2021 14:29
Show Gist options
  • Save d-rat/0a6bb692bbe54934f1f563fc475b3d43 to your computer and use it in GitHub Desktop.
Save d-rat/0a6bb692bbe54934f1f563fc475b3d43 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
firstMissingIndex
// Given an unsorted integer array nums, find the smallest missing positive integer.
// You must implement an algorithm that runs in O(n) time and uses constant extra space.
// https://leetcode.com/problems/first-missing-positive/
var firstMissingPositive = function (nums) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0 && nums[i] <= nums.length && nums[i] !== i + 1) {
[nums[i], nums[nums[i] - 1]] = [nums[nums[i] - 1], nums[i]];
i = i - 1;
}
}
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== j + 1) return j + 1;
}
return nums.length + 1;
};
// works for this
console.log(firstMissingPositive([1, 2, 0]));
// becomes infinite loop for this input
console.log(firstMissingPositive([3, 4, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment