For a given unsorted array, find the first k missing positive numbers in that array.

find-first-k-missing-positive.js

export function firstKMissingNumbers(arr, k) {
  // first we apply cycle sort to elements in range 0 < value <= arr.length
  // this way we ensure cycle sort is O(n)
  let i = 0;
  while (i < arr.length) {
    const value = arr[i];
    const index = arr[i] - 1;
    if (
      value !== i + 1 &&
      index >= 0 &&
      index < arr.length &&
      arr[index] !== index + 1
    ) {
      const tmp = arr[index];
      arr[index] = arr[i];
      arr[i] = tmp;
    } else {
      i += 1;
    }
  }

  // at this point all values in range 0 < value <= arr.length are at their correct places
  // correct place means value is at index value - 1 (1 is at 0, 2 is at 1 and so on)

  // create hash map of numbers in the array
  const map = {};
  for (let i = 0; i < arr.length; ++i) {
    map[arr[i]] = true;
  }

  // start building the result array of missing positive numbers
  // first iterate our partially sorted array
  // as soon as we encounter an index with value not equal to index + 1
  // it means value index + 1 is missing
  // add it to the missing numbers array
  const missingNumbers = [];
  for (let i = 0; i < arr.length; ++i) {
    const value = arr[i];
    if (value !== i + 1) {
      missingNumbers.push(i + 1);
    }
    // we already found k missing positive numbers, no need to continue
    if (missingNumbers.length === k) {
      break;
    }
  }

  // it is possible that we iterate our partially sorted array but still need more missing positive numbers
  // it means those numbers lie outside of the array
  // so start the loop from arr.length
  // and check hash map to verify the presence of the number
  // for example, if we have an array [1,2,3,7]
  // and we need 10 missing numbers,
  // by inspecting this array we can only tell that number 4 is missing (it should be where number 7 is)
  // we can see that number 7 is present, but it's not possible to place it at index 6, because we only have array of length 4
  // so we make a hash map
  // and then loop from array.length (4)
  // so we will check values 4+1 (5 - missing), 5+1 (6 - missing), 6+1 (7 - present in hash map), and so on
  // so 10 missing numbers will be [4,5,6,8,9,10,11,12,13,14]
  let j = arr.length;
  while (missingNumbers.length < k) {
    const value = j + 1;
    if (map[value] == null) {
      missingNumbers.push(value);
    }
    j += 1;
  }

  return missingNumbers;
}

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