Solution: Find the Corrupt Pair
Let's solve the Find the Corrupt Pair problem using the Cyclic Sort pattern.
We'll cover the following
Statement
We are given an unsorted array, nums
, with elements and each element is in the range inclusive. The array originally contained all the elements from to 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:
-
nums[i]
Solution
The given input array is unsorted, and the numbers in the input array lie in the range to . 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:
-
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 asnums[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 theSwap
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.
- The variable
-
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 to that index, the resulting value will be our missing number.
-
Return the pair containing missing and duplicated numbers.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.