We are given an unsorted array, nums, with n elements and each element is in the range [1,n] inclusive. The array originally contained all the elements from 1 to n but due to a data error, one of the numbers is duplicated, which causes another number missing. Find and return the corrupt pair (missing, duplicated).

corrupt-pair.js

export function findCorruptPair(nums) {
  let i = 0;

  // since our nums[i] is >= 1 and <= nums.length
  // we can apply cycle sort and remain O(n)
  // since we know that there is exactly one missing and one duplicated element
  // we sort our nums using cycle sort
  // and then find the first mismatch between an index and a value at the index
  // that first mismatch will give us the missing value (index+1), as well as the duplicated value nums[index]

  while (i < nums.length) {
    // current value
    const value = nums[i];

    // correct index of the current value
    const index = value - 1;

    // if current value is not at the correct index,
    // and value at the correct index is also not at the correct index,
    // swap values
    if (value !== i + 1 && nums[index] !== index + 1) {
      const tmp = nums[index];
      nums[index] = value;
      nums[i] = tmp;
    } else {
      i += 1;
    }
  }
  const missing = nums.findIndex((element, index) => element !== index + 1);
  return [missing + 1, nums[missing]];
}

// tc: O(n)
// sc: O(1)