Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * 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;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement