Given an unsorted integer array, arr, of size n and an integer k, find the first k missing positive integers from the array, ignoring all negative numbers and zeros.

If the array does not contain enough missing positive numbers, add the next consecutive positive integers, starting from the smallest number greater than the largest value in the array, until exactly k missing positive numbers have been found.

Return the list of the first k missing positive integers, sorted in ascending order.

Constraints:

• $n =$ arr.length

• $1 \leq k \leq 10^4$

• $-10^4 \leq$ arr[i] $\leq 10^4$

• $0 \leq n \leq 10^4$

The cyclic sort algorithm efficiently finds the first $k$ missing positive numbers from an unsorted array containing numbers within the range $1$ to $n$ (where $n$ is the the array’s length). The core idea is to place each valid number at its correct index — meaning the number $x$ should be positioned at index $x-1$. This process organizes the array such that all valid numbers fall into their correct place, making it easy to identify which numbers are missing.

After rearranging the array, any index $i$ where $arr[i] ≠ i + 1$ indicates that the number $i + 1$ is missing. If fewer than $k$ missing numbers are found within the array itself. In that case, the algorithm continues by adding consecutive numbers starting from $n + 1$, ensuring no duplicates, until exactly $k$ missing positive numbers have been identified.

The steps of the algorithm are as follows:

1. Initialize a result list, missing_nums, to store missing numbers and a set, extra_nums, to track duplicate or extra numbers. Also, initialize n with the length of the array.

2. Apply cyclic sort to place elements in their correct positions. For each element arr[i] in the array:

   1. If arr[i] is within the valid range (1 to n) and not already in its correct position (i.e., arr[i] != arr[arr[i] - 1]), we swap it with the element at its correct index.

   2. If arr[i] is out of range or already in its right position, we move to the next index.

3. After sorting, iterate through the arr again to identify the missing numbers:

   1. If the value at any index i does not match i + 1, it means i + 1 is missing, so we add it to the missing_nums list.

   2. Also, add the value at arr[i] to the extra_nums set to help avoid duplicates when checking for missing numbers beyond the array’s length.

   3. If the length of missing_nums reaches k, we stop the loop early, as we have already found the required number of missing positive numbers.

4. If we haven’t found k missing numbers from within the array, we continue searching for additional missing numbers starting from n + 1.

   1. Initialize num with n + 1 to check numbers beyond the array’s length.

   2. For each num, we check if it’s not in the extra_nums set (to avoid duplicates) and add it to the missing_nums list.

   3. Increment num by 1 and repeat the process until exactly k missing positive numbers are found.

5. Return the list, missing_nums, which contains exactly k missing numbers.

The slides below illustrate how we would like the algorithm to run: