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 nn elements and each element is in the range [1,n][1, n] inclusive. The array originally contained all the elements from 11 to nn 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≤n≤1032 \leq n \leq 10^3
  • 1≤1 \leq nums[i] ≤n\leq n

Solution#

The given input array is unsorted, and the numbers in the input array lie in the range 11 to nn. 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 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 11 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:

Created with Fabric.js 3.6.6 3 1 2 5 2 We have an unsorted array. Let's apply cyclicsort to find the corrupt pair. We'll keep elements at their correct index.

1 of 10

Created with Fabric.js 3.6.6 3 1 2 5 2 We’ve found that 3 isn’t at its correctposition, so we can swap it with the elementat index 2.

2 of 10

Created with Fabric.js 3.6.6 2 1 3 5 2 We’ve placed 3 at its correct position,but we need to check if the swapped element2 is now at its correct position.

3 of 10

Created with Fabric.js 3.6.6 2 1 3 5 2 We’ve found that 2 is not at its correct position, so we can swap it with the elementat index 1.

4 of 10

Created with Fabric.js 3.6.6 1 2 3 5 2 We’ve placed 2 at its correct position,but we need to check if the swapped element1 is now at its correct position.

5 of 10

Created with Fabric.js 3.6.6 1 2 3 5 2 Since 1 is already at its correct position,so we can traverse the array until we finda number that isn't.

6 of 10

Created with Fabric.js 3.6.6 1 2 3 5 2 We’ve found that 5 is not at its correct position, so we can swap it with the elementat index 4.

7 of 10

Created with Fabric.js 3.6.6 1 2 3 2 5 We’ve placed 5 at its correct position,but we need to check if the swapped element2 is now at its correct position.

8 of 10

Created with Fabric.js 3.6.6 1 2 3 2 5 Now, the number 2 present at index 3 is at incorrect position. 2 also exists at a correct position in the array,so we have identified this as the duplicate number. We can conclude that the index that contains the incorrect number should have held the missing numberand can be calculated by index + 1.

9 of 10

Created with Fabric.js 3.6.6 1 2 3 2 5 The missing number calculated by index + 1( 3+1) is 4 and the duplicate number present is 2.

10 of 10

Find the Corrupt Pair

Time complexity#

The time complexity of the above solution is O(n)O({n}), because it uses the cyclic sort, where nn is the size of the array. In the worst case, let’s assume that every element is placed at the wrong index. With every swap operation, there is at least one element that is placed in the right place. The total number of swap operations that need to be performed is O(n)O(n).

Space complexity#

The space complexity of the above solution is O(1)O(1), because we have used constant space.

Find the Corrupt Pair

First Missing Positive