Find the Corrupt Pair
Explore how to find the corrupt pair—a missing and a duplicated number—in an unsorted array using cyclic sort. This lesson helps you understand the problem constraints and apply sorting logic to efficiently detect errors, preparing you for common coding interview challenges.
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]
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Find the Corrupt Pair
Which is the corrupt pair in the array given below?
[4, 1, 3, 4, 5]
2, 3
2, 4
2, 5
2, 6
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
#include <iostream>#include <vector>vector<int> FindCorruptPair(vector<int> nums){// Replace this placeholder return statement with your codereturn {-1, -1};}