Tasks

Cyclic Sort

// 268. Missing Number
// Time: O(n) | Space: O(1)

var missingNumber = function(nums) {
  // Get the length of the 'nums' array.
  const length = nums.length;
  
  // Initialize 'index' to start from the beginning of the array.
  let index = 0;
  
  // Process each element in the 'nums' array.
  while (index < length) {
    // At the beginning of each loop iteration, get the value of the element at the current 'index'.
    let value = nums[index];
  
    // If the 'value' is within the bounds of the array and 
    // the value is not already in its correct position (i.e., nums[value] != value)
    // then swap it with the element in its correct position.
    if (value < length && value !== nums[value]) {
        [nums[index], nums[value]] = [nums[value], nums[index]]; // Swap the elements.
    } else {
      // If the 'value' is out of bounds or already in its correct position,
      // move to the next index.
      index += 1;
    }
  }
  
  // After the above loop, numbers should be in their correct positions if they exist in the array.
  // Now, we iterate through the 'nums' array again to find the first misplaced number.
  for (let i = 0; i < length; i++) {
    // If the number isn't in its correct position (i.e., index != value), return the index.
    if (i != nums[i]) {
        return i;
    }
  }
  
  // If all numbers are in their correct positions and no index is missing,
  // then the smallest missing positive is 'length'.
  return length;
}

// 41. First Missing Positive

// Cyclic Sort
// Time: O(n) | Space: O(1)
var firstMissingPositive = function(nums) {
    // Initialize index 'i' to start from the beginning of the 'nums' array.
    let i = 0;

    // Process each element in the 'nums' array to place each positive integer in its correct position.
    while (i < nums.length) {
        // Calculate the correct position for the value at 'nums[i]'.
        // (Subtracting 1 since array indices are 0-based).
        const correctSpot = nums[i] - 1;

        // Check if the value at 'nums[i]' should be placed elsewhere (i.e., it's not negative, 
        // not too large, and not already in its correct position).
        if (correctSpot >= 0 && correctSpot < nums.length && nums[i] !== nums[correctSpot]) {
            // Swap the value 'nums[i]' with the value in its correct position 'nums[correctSpot]'.
            [nums[i], nums[correctSpot]] = [nums[correctSpot], nums[i]];
        } else {
            // If 'nums[i]' is already in its correct spot or out of the desired range,
            // move to the next index.
            i++;
        }
    }

    // After rearranging the 'nums' array, iterate through it 
    // to find the smallest missing positive integer.
    for (let i = 0; i < nums.length; i++) {
        // If the current index (plus 1, to account for 1-based positive integers) 
        // doesn't match the value at that index, that means 'i + 1' 
        // is the smallest missing positive integer.
        if (i + 1 !== nums[i]) {
            return i + 1;
        }
    }

    // If all positions from 1 up to 'nums.length' are filled properly, then 
    // the smallest missing positive integer is 'nums.length + 1'.
    return nums.length + 1;
};

// Find the Corrupt Pair

// Time: O(n) | Space: O(1)
export function findCorruptPair(nums){
  // Initialize 'missing' and 'duplicated' to null, to store the results once identified.
  let missing = null;
  let duplicated = null;

  // Helper function to swap two values in an array.
  function swap(arr, first, second) {
    [arr[first], arr[second]] = [arr[second], arr[first]];
  }

  // Initialize an index 'i' starting from 0.
  let i = 0;
  // Process each element in the 'nums' array to place each number in its correct position.
  while (i < nums.length) {
    // Calculate the correct position for the value at 'nums[i]'.
    // (Subtracting 1 because array indices are 0-based).
    let correct = nums[i] - 1;
    
    // If the current value is not in its correct position, swap it with the value in its correct position.
    if (nums[i] != nums[correct]) {
      swap(nums, i, correct);
    } else {
      // If the current value is in its correct position, move to the next index.
      i += 1;
    }
  }

  // After placing numbers in their correct positions, iterate through the 'nums' array to identify the missing and duplicated numbers.
  for (let j = 0; j < nums.length; j++) {
    // If the current position doesn't have its correct value,
    // then 'j + 1' is the missing number and 'nums[j]' is the duplicated one.
    if (nums[j] != j + 1) {
      duplicated = nums[j];
      missing = j + 1;
    }
  }

  // Return the result as an array containing the missing and duplicated numbers.
  return [missing, duplicated];
}

// Find the First K Missing Positive Numbers

// Time: O(n) | Space: O(n)
export function firstKMissingNumbers(nums, k) {
    let n = nums.length;
    let i = 0;

    // Cyclically sort the positive numbers
    while (i < n) {
        let correct = nums[i] - 1;
        if (nums[i] > 0 && nums[i] <= n && nums[i] !== nums[correct]) {
            [nums[i], nums[correct]] = [nums[correct], nums[i]]; // swap
        } else {
            i++;
        }
    }

    const missingNumbers = [];

    // Find the first k positive missing numbers
    for (i = 0; i < n && missingNumbers.length < k; i++) {
        if (nums[i] !== i + 1) {
            missingNumbers.push(i + 1);
        }
    }

    // If we still haven't found k missing numbers, add the remaining ones
    // which are more than the maximum number present in the array.
    while (missingNumbers.length < k) {
        missingNumbers.push(i + 1);
        i++;
    }

    return missingNumbers;
}