Find the Corrupt Pair (Custom Variant)

▶

Steps

setup

Initialize index i and array length n

Set the starting index i to 0 and determine the length n of the array to control the sorting loop.

💡 Initialization sets up the loop boundaries and starting point for the cyclic sort process.

Line:

i = 0
n = len(nums)

💡 We begin processing from the first element and know how many elements to process.

compare

Calculate correct index for nums[i]

Calculate the correct index for the current number nums[i] by subtracting 1 from its value.

💡 This calculation determines where the current number should be placed in the array.

Line:

correct_index = nums[i] - 1

💡 Each number from 1 to n has a unique correct index equal to number - 1.

compare

Check if nums[i] != nums[correct_index]

Compare the current number with the number at its correct index to decide if a swap is needed.

💡 If they differ, the current number is not in the right place and should be swapped.

Line:

if nums[i] != nums[correct_index]:

💡 A mismatch means the current number is misplaced and swapping will move it closer to correct position.

swap

Swap nums[i] and nums[correct_index]

Swap the current number with the number at its correct index to move it closer to its correct position.

💡 Swapping places the current number where it belongs and brings a new number to index i for checking.

Line:

nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Swapping is the core operation that gradually sorts the array in-place.

compare

Calculate correct index for new nums[i]

Calculate the correct index for the new number at index i after the swap.

💡 We must check if the new number at i is in the correct position or needs another swap.

Line:

correct_index = nums[i] - 1

💡 Each swap may bring a new number to i that needs to be placed correctly.

compare

Check if nums[i] != nums[correct_index]

Compare the current number with the number at its correct index to decide if another swap is needed.

💡 If they differ, we swap again; otherwise, we move i forward.

Line:

if nums[i] != nums[correct_index]:

💡 Multiple swaps may be needed to place numbers correctly.

swap

Swap nums[i] and nums[correct_index]

Swap the current number with the number at its correct index to continue sorting.

💡 This swap places 2 and 1 in their correct positions.

Line:

nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Swapping continues until the number at i is correct or a duplicate is detected.

compare

Calculate correct index for new nums[i]

Calculate the correct index for the new number at index i after the swap.

💡 We check if the new number at i is in the correct position.

Line:

correct_index = nums[i] - 1

💡 If the number is already correct, we move i forward.

compare

Check if nums[i] != nums[correct_index]

Compare the current number with the number at its correct index to decide if a swap is needed.

💡 Since nums[i] equals nums[correct_index], no swap is needed and we move i forward.

Line:

if nums[i] != nums[correct_index]:
    ...
else:
    i += 1

💡 When the number is in the correct place, we proceed to the next index.

compare

Calculate correct index for nums[i]

Calculate the correct index for the current number at i=1.

💡 We find the target position for nums[1] = 2.

Line:

correct_index = nums[i] - 1

💡 The correct index for 2 is 1.

compare

Check if nums[i] != nums[correct_index]

Compare nums[1] with nums[1] to decide if swap is needed.

💡 Since they are equal, move i forward.

Line:

if nums[i] != nums[correct_index]:
    ...
else:
    i += 1

💡 Correct placement means advancing the pointer.

compare

Calculate correct index for nums[i]

Calculate the correct index for nums[2] = 3.

💡 We find the target position for 3.

Line:

correct_index = nums[i] - 1

💡 Correct index for 3 is 2.

compare

Check if nums[i] != nums[correct_index]

Compare nums[2] with nums[2] to decide if swap is needed.

💡 They are equal, so move i forward.

Line:

if nums[i] != nums[correct_index]:
    ...
else:
    i += 1

💡 Correct placement means advancing the pointer.

compare

Calculate correct index for nums[i]

Calculate the correct index for nums[3] = 5.

💡 We find the target position for 5.

Line:

correct_index = nums[i] - 1

💡 Correct index for 5 is 4.

compare

Check if nums[i] != nums[correct_index]

Compare nums[3] with nums[4] to decide if swap is needed.

💡 They differ, so swap to place 5 correctly.

Line:

if nums[i] != nums[correct_index]:

💡 Swapping moves 5 to its correct position and brings a new number to i.

swap

Swap nums[i] and nums[correct_index]

Swap the numbers at indices 3 and 4 to place 5 correctly.

💡 This swap moves 5 to index 4 and brings 3 to index 3 for checking.

Line:

nums[i], nums[correct_index] = nums[correct_index], nums[i]

💡 Swapping handles duplicates by placing numbers in their correct spots or revealing duplicates.

compare

Calculate correct index for new nums[i]

Calculate the correct index for nums[3] = 3 after the swap.

💡 We check if the new number at i is in the correct position or a duplicate.

Line:

correct_index = nums[i] - 1

💡 The correct index for 3 is 2.

compare

Check if nums[i] != nums[correct_index]

Compare nums[3] with nums[2] to decide if swap is needed.

💡 They are equal, indicating a duplicate; move i forward to continue.

Line:

if nums[i] != nums[correct_index]:
    ...
else:
    i += 1

💡 Duplicate detected because the number is already at its correct index.

compare

Calculate correct index for nums[i]

Calculate the correct index for nums[4] = 5.

💡 We find the target position for 5.

Line:

correct_index = nums[i] - 1

💡 Correct index for 5 is 4.

compare

Check if nums[i] != nums[correct_index]

Compare nums[4] with nums[4] to decide if swap is needed.

💡 They are equal, so move i forward to finish sorting.

Line:

if nums[i] != nums[correct_index]:
    ...
else:
    i += 1

💡 All numbers are now in their correct or duplicate positions.

traverse

Traverse array to find corrupt pair

Scan the sorted array to find the first index where nums[i] != i + 1, indicating the duplicate and missing numbers.

💡 This final scan identifies the corrupt pair by comparing values to expected positions.

Line:

for i in range(n):
    if nums[i] != i + 1:
        return [nums[i], i + 1]

💡 Mismatch between value and index+1 reveals the corrupt pair.

def find_corrupt_pair(nums):
    i = 0  # STEP 1
    n = len(nums)  # STEP 1
    while i < n:  # STEP 2 loop
        correct_index = nums[i] - 1  # STEP 2
        if nums[i] != nums[correct_index]:  # STEP 3 decision
            nums[i], nums[correct_index] = nums[correct_index], nums[i]  # STEP 4 swap
        else:
            i += 1  # STEP 9,11,13,18,20 move pointer
    for i in range(n):  # STEP 21 traverse
        if nums[i] != i + 1:
            return [nums[i], i + 1]  # STEP 21 return corrupt pair
    return [-1, -1]

📊

Find the Corrupt Pair (Custom Variant) - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement reveals how cyclic sort efficiently detects the corrupt pair without extra space or sorting overhead.

setup

i

3

0

1

1

2

2

5

3

3

4

compare

i

3

0

1

1

correct_index

2

2

5

3

3

4

compare

i

3

0

1

1

correct_index

2

2

5

3

3

4

swap

i

2

0

correct_index

1

1

3

2

5

3

3

4

compare

i

2

0

correct_index

1

1

3

2

5

3

3

4

compare

i

2

0

correct_index

1

1

3

2

5

3

3

4

swap

i

1

0

2

1

3

2

5

3

3

4

compare

correct_index

1

0

2

1

3

2

5

3

3

4

move_right

1

0

i

2

1

3

2

5

3

3

4

compare

1

0

correct_index

2

1

3

2

5

3

3

4

move_right

1

0

2

1

i

3

2

5

3

3

4

compare

1

0

2

1

correct_index

3

2

5

3

3

4

move_right

1

0

2

1

3

2

i

5

3

3

4

compare

1

0

2

1

3

2

i

5

3

correct_index

3

4

compare

1

0

2

1

3

2

i

5

3

correct_index

3

4

swap

1

0

2

1

correct_index

3

2

i

3

3

5

4

compare

1

0

2

1

correct_index

3

2

i

3

3

5

4

move_right

1

0

2

1

3

2

3

3

i

5

4

compare

1

0

2

1

3

2

3

3

correct_index

5

4

move_right

1

0

2

1

3

2

3

3

5

4

compare

1

0

2

1

3

2

i

3

3

5

4

Result: [3,4]

Key Takeaways

✓ Cyclic sort places each number at its correct index by swapping in-place without extra space.

This insight is hard to see from code alone because the swapping logic is subtle and happens conditionally.

✓ The pointer 'i' only moves forward when the current number is correctly placed or a duplicate is detected.

Visualizing pointer movement clarifies why some indices are revisited multiple times.

✓ The corrupt pair is identified by scanning for the first mismatch between value and expected index+1 after sorting.

This final step reveals the problem's solution clearly, which can be missed if only reading code.

Practice

1. Given the following Python function implementing cyclic sort with extra space, what is the output when the input array is [2, 3, 1]?

def cyclic_sort_extra_space(arr):
    n = len(arr)
    result = [0] * n
    for num in arr:
        if 1 <= num <= n:
            result[num - 1] = num
    return result

print(cyclic_sort_extra_space([2, 3, 1]))

easy

A. [2, 3, 1]

B. [3, 1, 2]

C. [0, 0, 0]

D. [1, 2, 3]

Solution

1. Step 1: Initialize result array

   result = [0, 0, 0], n = 3

2. Step 2: Place each number at index num-1

   num=2 -> result[1]=2; num=3 -> result[2]=3; num=1 -> result[0]=1; final result = [1, 2, 3]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All numbers placed at correct indices [OK]

Hint: Index num-1 placement yields sorted array [OK]

Common Mistakes:

• Off-by-one index errors
• Returning original array
• Not initializing result array correctly

2. You are given an array of integers where each integer is between 1 and n (inclusive), and some elements appear twice while others appear once. Which algorithmic approach guarantees finding all duplicate elements in O(n) time and O(1) extra space?

easy

A. Cyclic sort to place each number at its correct index, then scanning for mismatches

B. Using a hash set to track seen elements and identify duplicates

C. Sorting the array and then scanning for consecutive duplicates

D. Applying a dynamic programming approach to count occurrences

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 1 to n, allowing index-based placement.

2. Step 2: Identify approach that uses in-place swaps

   Cyclic sort places each number at index = number - 1, enabling O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort exploits value-index mapping for optimal duplicate detection [OK]

Hint: Use cyclic sort for O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is always O(n) time
• Believing hash sets use O(1) space
• Confusing DP applicability for duplicates

3. If the input array can contain numbers outside the range 1 to n (including negatives and zeros), which modification to the cyclic sort approach correctly finds all missing numbers in [1, n]?

hard

A. Ignore numbers outside 1 to n during swaps and only swap valid numbers

B. Use a hash set to track all numbers instead of cyclic sort

C. Replace invalid numbers with n+1 before cyclic sort to avoid errors

D. Sort the array first to bring valid numbers to front, then apply cyclic sort

Solution

1. Step 1: Identify invalid numbers impact

   Numbers outside 1 to n cause index errors or invalid swaps in cyclic sort.

2. Step 2: Modify cyclic sort to skip invalid numbers

   Only swap when nums[i] is in [1, n]; ignore or increment i otherwise to maintain O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring invalid numbers preserves cyclic sort correctness [OK]

Hint: Skip invalid numbers to avoid index errors [OK]

Common Mistakes:

• Using hash set loses O(1) space
• Replacing invalid numbers breaks uniqueness
• Sorting adds O(n log n) time

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

5. If the input array can contain numbers reused multiple times (duplicates can appear more than once), which modification to the cyclic sort approach correctly finds one duplicate and one missing number?

hard

A. Use a frequency array to count occurrences instead of cyclic sort

B. Modify cyclic sort to skip swapping when nums[i] == nums[correct] to avoid infinite loops

C. Run cyclic sort multiple times until no swaps occur

D. Sort the array and scan for duplicates and missing numbers

Solution

1. Step 1: Understand the problem extension

   Multiple duplicates break naive cyclic sort because repeated swaps cause infinite loops.

2. Step 2: Modify cyclic sort to skip swapping when duplicate detected

   Adding a check to skip swapping if nums[i] == nums[correct] prevents infinite loops and still finds mismatch.

3. Step 3: Contrast other options

   Frequency array uses extra space, multiple runs are inefficient, sorting is O(n log n).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Skipping swaps on duplicates fixes infinite loop in cyclic sort [OK]

Hint: Skip swaps when duplicate detected to avoid infinite loops [OK]

Common Mistakes:

• Assuming cyclic sort works unchanged with multiple duplicates
• Relying on multiple passes instead of fixing swap condition
• Ignoring space constraints by using frequency arrays