daniel-g-lee
6/6/2019 - 4:42 AM

First Missing Positive

/**
 * So basically, we want to first turn all values < 0 to null.
 * Then, using 1-indexing (First value of array is index 1 instead of 0), we change the number to a negative. The reason being is
 * that we want to hit either the first null or first positive, which indicates that that is the first number missing. A positive
 * number in the array will always change the value of the index it references to a negative, so the first value hit, which is the
 * first number missing, will always be either null or a positive value.
 * When changing the values to negatives, if the value is positive, we need to replace whatever value is there with a negative version
 * of itself. This is because we may pass over that number, and will need the original value, but also need to show that it should
 * be skipped in the final pass.
 * Lastly, the last step is to find either a number that is positive or null. A base case exists where if the array were empty, the
 * array were all null, or the array were all negative, it would always be 1.
 * */
var firstMissingPositive = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= 0) {
            nums[i] = null;
        }
    }
    
    console.log("Nums after first pass: ", nums);
    
    for (let i = 0; i < nums.length; i++) {
      console.log("Current iteration: ", i, "\tNum: ", nums[i]);
        if (nums[i] !== null) {
          console.log("nums[Math.abs(", nums[i], ") - 1]): ", nums[Math.abs(nums[i]) - 1])
            if (nums[Math.abs(nums[i]) - 1] > 0) {
                console.log("Changing ", nums[Math.abs(nums[i]) - 1], " to ", -nums[Math.abs(nums[i]) - 1])
                nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
            } else if (nums[Math.abs(nums[i]) - 1] === null) {
                console.log("Value is null, changing to negative length: ", -(nums.length));
                nums[Math.abs(nums[i]) - 1] = -(nums.length);
            } else {
              console.log("Will not do anything. Num either undefined or negative.")
            }
        } else {
          console.log("Pass");
        }
        console.log("Nums at end of iteration ", i, ": ", nums);
    }
    
    console.log("Nums after second pass: ", nums);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0 || nums[i] === null) {
            return i + 1;
        }
    }
    
    return nums.length + 1;
};