Simple JavaScript O(n) time and O(1) space


  • 0
    var firstMissingPositive = function(nums) {
        let i = 0;
        while (i < nums.length) {
            if (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
                [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
            } else {
                i++;
            }
        }
        for (i = 0; i < nums.length; i++) {
            if (nums[i] !== i + 1) return i + 1;
        }
        return i + 1;
    };
    
    1. Go through and place each number at the index of its value (minus one since 0 isn't positive). All the negative and out-of-bounds elements should now be in the missing gap or on the right side of the array.
    2. Walk through and take the first index (plus one) which does not match its associated value.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.