Solution: Find the Corrupt Pair

Statement

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).

Constraints:

• $2 \leq n \leq 10^3$
• $1 \leq$ nums[i] $\leq n$

Solution

The given input array is unsorted, and the numbers in the input array lie in the range $1$ to $n$. Therefore, the cyclic sort is optimal to place the elements at their correct index. Once all the elements are in their correct position, we can easily find the pair of missing and duplicate numbers.

The essence of this approach is to identify missing and duplicated elements within a single pass. This approach involves iteratively swapping elements until each number is placed at its correct index. After this, it scans the array to find the element that does not match its index, indicating the presence of a duplicate. Simultaneously, this also points to the absence of the number that should have been at this index, identifying the missing number.

The steps of the above-mentioned approach are given below:

1. The first step is to place each number in its correct position during the cyclic sort. Initialize i to 0 and iterate over the array. While traversing, we will perform the following steps:

   • The variable correct is calculated as nums[i] - 1, representing the index where the current number should be placed if the array were sorted.
   • If the current number, nums[i], is not equal to the number at the correct position, nums[correct], a swap is performed using the Swap function to move the current number to its correct position.
   • If the numbers are already in their correct positions, i is incremented to move to the next element.

2. The second step is to traverse the array and detect the number that is not at its correct index. This will be the duplicated number. When we add $1$ to that index, the resulting value will be our missing number.

3. Return the pair containing missing and duplicated numbers.

Let’s look at the following illustration to get a better understanding of the solution: