Find the Corrupt Pair (Custom Variant)

📋

Problem

Imagine a warehouse inventory system where each item should have a unique ID from 1 to n, but due to a scanning error, one ID is duplicated and another is missing. You need to find both the duplicate and the missing IDs to fix the records.

Given an array of size n containing numbers from 1 to n, exactly one number is duplicated and one number is missing. Find the duplicate number and the missing number and return them as a pair [duplicate, missing].

1 ≤ n ≤ 10^5Array elements are integers in the range [1, n]Exactly one number is duplicated and exactly one number is missing

Edge cases: Array with minimum size n=2, e.g. [2, 2] → duplicate=2, missing=1Duplicate is the last number, e.g. [1, 2, 3, 4, 4] → duplicate=4, missing=5Duplicate is the first number, e.g. [1, 1, 3, 4, 5] → duplicate=1, missing=2

</>

IDE

def find_corrupt_pair(nums: list[int]) -> list[int]:public int[] findCorruptPair(int[] nums)vector<int> findCorruptPair(vector<int>& nums)function findCorruptPair(nums)

def find_corrupt_pair(nums):
    # Write your solution here
    pass

class Solution {
    public int[] findCorruptPair(int[] nums) {
        // Write your solution here
        return new int[]{-1, -1};
    }
}

#include <vector>
using namespace std;

vector<int> findCorruptPair(vector<int>& nums) {
    // Write your solution here
    return {-1, -1};
}

function findCorruptPair(nums) {
    // Write your solution here
    return [-1, -1];
}

Common Bugs to Avoid

Wrong: [3, 5]Incorrectly identifying missing number as last element without checking all indices.✅ After cyclic sort, scan entire array for first index i where nums[i] != i+1 to find missing number.

Wrong: [2, 2]Returning duplicate number as missing number due to not scanning for missing after sorting.✅ Ensure missing number is identified as index+1 where mismatch occurs, not duplicate number.

Wrong: [-1, 1]Failing to detect duplicate number when duplicate is at start or end.✅ Use cyclic sort swaps until each number is at correct index; then find mismatch for duplicate and missing.

Wrong: Infinite loop or timeoutNot checking if nums[i] == nums[correctIndex] before swapping, causing infinite swaps.✅ Add condition to swap only if nums[i] != nums[correctIndex].

Wrong: [1, 1]Off-by-one error in indexing causing duplicate and missing to be same number.✅ Compare nums[i] with i+1, not i, when scanning for mismatch.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Watch out for indexing errors and infinite loops in cyclic sort.

Optimize your solution to linear time using cyclic sort.

t1_01basic

Input[3,1,2,5,3]

Expected[3,4]

⏱ Performance - must finish in 2000ms

3 is duplicated and 4 is missing from the sequence 1 to 5.

💡 Try placing each number at its correct index to identify anomalies.

💡 Use cyclic sort to place numbers and detect the duplicate and missing.

💡 After sorting, the index where nums[i] != i+1 reveals the corrupt pair.

Why it failed: Incorrect output means the algorithm failed to detect the duplicate or missing number correctly. Fix by ensuring the cyclic sort swaps until each number is at its correct index and then identify the mismatch.

✓ Correctly identified the duplicate and missing numbers using cyclic sort.

t1_02basic

Input[1,2,2,4,5]

Expected[2,3]

⏱ Performance - must finish in 2000ms

2 is duplicated and 3 is missing from the sequence 1 to 5.

💡 Check for the first index where the number is not equal to index+1 after sorting.

💡 Use cyclic sort to place numbers in their correct positions.

💡 The duplicate is the number at the mismatched index; missing is index+1.

Why it failed: Output wrong because the code did not correctly identify the missing number when duplicate appears before it. Fix by scanning after cyclic sort to find the first mismatch.

✓ Correctly found the duplicate and missing numbers even when duplicate is before missing.

t2_01edge

Input[2,2]

Expected[2,1]

⏱ Performance - must finish in 2000ms

Minimum size array with duplicate 2 and missing 1.

💡 Test the smallest input size to ensure base cases are handled.

💡 Check if your code handles arrays of length 2 correctly.

💡 Make sure cyclic sort works even when n=2 and detects duplicate and missing.

Why it failed: Fails on minimum size input due to missing base case handling. Fix by ensuring the algorithm works for n=2 and does not assume larger arrays.

✓ Handles minimum size input correctly.

t2_02edge

Input[1,2,3,4,4]

Expected[4,5]

⏱ Performance - must finish in 2000ms

Duplicate is the last number 4; missing number is 5.

💡 Check boundary conditions where duplicate is at the end of the array.

💡 Verify that your code correctly identifies missing number beyond last index.

💡 After cyclic sort, check for missing number equal to n if no mismatch found earlier.

Why it failed: Fails to detect missing number at the end when duplicate is last. Fix by checking if last element is not equal to n after sorting.

✓ Correctly identifies duplicate at end and missing number n.

t2_03edge

Input[1,1,3,4,5]

Expected[1,2]

⏱ Performance - must finish in 2000ms

Duplicate is the first number 1; missing number is 2.

💡 Test case where duplicate is at the start of the array.

💡 Ensure cyclic sort swaps correctly even when duplicate is at index 0.

💡 Look for the first index where nums[i] != i+1 to find missing number.

Why it failed: Fails when duplicate is at the start due to incorrect swap logic. Fix by ensuring swap only occurs if nums[i] != nums[correctIndex].

✓ Correctly handles duplicate at start and finds missing number.

t3_01corner

Input[1,3,3,4,5]

Expected[3,2]

⏱ Performance - must finish in 2000ms

Duplicate 3 and missing 2; tests off-by-one errors in indexing.

💡 Check if your indexing is zero-based but values are one-based.

💡 Verify that you compare nums[i] with i+1, not i.

💡 Fix off-by-one by always comparing nums[i] to i+1 when scanning after cyclic sort.

Why it failed: Off-by-one error causes wrong missing number detection. Fix by using i+1 instead of i when comparing indices to values.

✓ Correctly handles indexing and finds duplicate and missing.

t3_02corner

Input[2,2,2,4,5]

Expected[2,3]

⏱ Performance - must finish in 2000ms

Multiple duplicates of the same number (invalid input but tests robustness).

💡 Check if your code assumes exactly one duplicate and one missing.

💡 Ensure your code does not enter infinite loops when duplicates repeat.

💡 Add condition to break swaps if nums[i] == nums[correctIndex] to avoid infinite loops.

Why it failed: Infinite loop or incorrect output due to repeated duplicates. Fix by adding check to skip swap if nums[i] == nums[correctIndex].

✓ Handles repeated duplicates gracefully without infinite loops.

t3_03corner

Input[1,2,3,4,5]

Expected[-1,-1]

⏱ Performance - must finish in 2000ms

No duplicate or missing number (invalid input) to test graceful failure.

💡 Check how your code behaves if input is already correct.

💡 Return [-1, -1] or similar to indicate no corrupt pair found.

💡 Add a final check after cyclic sort to return [-1, -1] if no mismatch found.

Why it failed: Code returns incorrect duplicate/missing when none exist. Fix by returning [-1, -1] if no mismatch found after sorting.

✓ Gracefully handles no corrupt pair scenario.

t4_01performance

Input[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) cyclic sort must complete within 2 seconds.

💡 Use cyclic sort to achieve O(n) time complexity.

💡 Avoid nested loops or sorting algorithms with O(n log n) or worse.

💡 Ensure swaps only occur when nums[i] != nums[correctIndex].

Why it failed: TLE due to using sorting or nested loops with O(n log n) or O(n^2). Fix by implementing cyclic sort with O(n) complexity.

✓ Algorithm runs in O(n) time as expected.

Practice

1. Given the following code snippet, what is the output when calling findDisappearedNumbers([2,3,2,1])?

easy

A. [4,2]

B. [4]

C. [3,4]

D. [1,4]

Solution

1. Step 1: Trace swaps in the while loop

   Initial array: [2,3,2,1] - i=0: nums[0]=2, correct=1; swap nums[0] and nums[1] -> [3,2,2,1] - i=0: nums[0]=3, correct=2; swap nums[0] and nums[2] -> [2,2,3,1] - i=0: nums[0]=2, correct=1; nums[0]==nums[1], so i=1 - i=1: nums[1]=2, correct=1; nums[1]==nums[1], i=2 - i=2: nums[2]=3, correct=2; nums[2]==nums[2], i=3 - i=3: nums[3]=1, correct=0; swap nums[3] and nums[0] -> [1,2,3,2] - i=3: nums[3]=2, correct=1; nums[3]==nums[1], i=4 (end)

2. Step 2: Identify missing numbers

   Final array: [1,2,3,2] Check indices: - i=0: 1 == 1 - i=1: 2 == 2 - i=2: 3 == 3 - i=3: 2 != 4 -> missing number is 4

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 4 is missing from 1 to 4 [OK]

Hint: Trace swaps carefully to find final array [OK]

Common Mistakes:

• Off-by-one in missing number
• Confusing duplicates with missing
• Stopping swaps too early

2. You are given an unsorted array of integers that may contain duplicates, negatives, and zeros. Your task is to find the smallest continuous range of positive integers that are missing from the array. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Using a hash set to store all positive numbers and then checking for the missing range

B. Sorting the array and then scanning linearly to find the missing range

C. Using a dynamic programming approach to track presence of numbers

D. Using cyclic sort to place each positive integer at its correct index and then scanning for the missing range

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest missing positive range in O(n) time and O(1) space, which excludes sorting (O(n log n)) and hash sets (O(n) space).

2. Step 2: Identify the algorithm that achieves in-place linear time

   Cyclic sort places each positive integer at its correct index in the array, enabling a single pass to find the missing range efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort is known for in-place linear time sorting of numbers in range 1 to n [OK]

Hint: Cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Common Mistakes:

• Assuming sorting is optimal
• Confusing hash set space with time complexity

3. Given the following code snippet, what is the output when calling findErrorNums([1, 2, 2, 4])?

easy

A. [2, 4]

B. [3, 2]

C. [2, 3]

D. [1, 3]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [1, 2, 2, 4]. The duplicate 2 causes a swap to place numbers correctly except index 2 which remains 2.

2. Step 2: Identify mismatch after sorting

   After sorting, array is [1, 2, 2, 4]. At index 2, expected 3 but found 2 -> duplicate=2, missing=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing pair [OK]

Hint: Mismatch found where index+1 != value after cyclic sort [OK]

Common Mistakes:

• Confusing duplicate and missing order
• Off-by-one errors in indexing
• Returning wrong pair from loop

4. Suppose the problem changes: the array can contain repeated numbers that can be reused infinitely many times. Which modification to the optimal approach is necessary to correctly find the first k missing positive numbers?

hard

A. Use a frequency map instead of cyclic sort to track counts and find missing numbers.

B. Keep the cyclic sort but add a visited set to avoid infinite swaps due to reuse.

C. Replace cyclic sort with a brute force check for each number from 1 upwards until k missing are found.

D. Use a priority queue to generate missing numbers dynamically considering reuse.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means cyclic sort assumptions break because numbers can appear multiple times and be reused infinitely.

2. Step 2: Identify correct approach

   A frequency map tracks counts of each number, allowing detection of missing positives even with infinite reuse.

3. Step 3: Why other options fail

   Adding visited set won't prevent infinite swaps due to reuse. Brute force is inefficient. Priority queue adds overhead without correctness guarantee.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map handles reuse correctly and efficiently [OK]

Hint: Reuse breaks cyclic sort; frequency map needed [OK]

Common Mistakes:

• Trying to patch cyclic sort with visited sets
• Assuming brute force is acceptable for large k
• Using priority queues unnecessarily

5. If the problem is changed so that numbers can appear multiple times (duplicates can appear more than twice), which modification to the cyclic sort approach is necessary to correctly find any duplicate?

hard

A. Use Floyd's Tortoise and Hare algorithm instead because cyclic sort fails with multiple duplicates

B. No modification needed; the current cyclic sort approach works for multiple duplicates

C. Modify the code to continue scanning after finding the first duplicate to find all duplicates

D. Add a hash set to track visited numbers since cyclic sort assumes only one duplicate

Solution

1. Step 1: Understand cyclic sort assumption

   Cyclic sort assumes exactly one duplicate; multiple duplicates break the unique mapping to indices.

2. Step 2: Identify solution for multiple duplicates

   Using a hash set tracks seen numbers and detects any duplicate regardless of count.

3. Step 3: Why other options fail

   Continuing cyclic sort won't find all duplicates; Floyd's algorithm detects one cycle only; no modification fails on multiple duplicates.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Hash set handles multiple duplicates correctly [OK]

Hint: Cyclic sort assumes one duplicate; hash set needed for multiple [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged for multiple duplicates
• Thinking Floyd's algorithm finds all duplicates
• Trying to modify cyclic sort without extra space