Find Duplicate and Missing (Two Issues)

▶

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.

💡 Initializing i and n sets up the iteration boundaries for the cyclic sort process.

Line:

i = 0
n = len(nums)

💡 We will process the array from left to right using i as the current index.

compare

Calculate correct index for nums[i]

Calculate the correct index for the number at index i=0, which is nums[0] = 3, so correct_index = 2.

💡 Finding the correct index helps us know where this number should be placed in the array.

Line:

correct_index = nums[i] - 1

💡 The number 3 should be at index 2 (0-based).

compare

Check if swap needed at i=0

Compare nums[i] (3) with nums[correct_index] (nums[2] = 2). Since they differ, we will swap to place 3 correctly.

💡 Swapping moves numbers closer to their correct positions, which is the core of cyclic sort.

Line:

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

💡 Swapping is necessary to move 3 to index 2 and bring 2 to index 0.

swap

Swap nums[i] and nums[correct_index]

Swap nums[0] and nums[2], placing 3 at index 2 and 2 at index 0.

💡 This swap moves the number 3 closer to its correct position and brings 2 to be processed next.

Line:

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

💡 After swap, the number at index i might still be incorrect, so we do not increment i yet.

compare

Calculate new correct index for nums[i]

Now nums[i] = 2 at index 0, so correct_index = 1. We check if a swap is needed again.

💡 We repeat the process until the number at i is correctly placed or a duplicate is detected.

Line:

correct_index = nums[i] - 1

💡 The number 2 should be at index 1.

compare

Check if swap needed at i=0 again

Compare nums[i] (2) with nums[correct_index] (nums[1] = 1). They differ, so swap is needed.

💡 Swapping again moves 2 to its correct position and brings 1 to index 0.

Line:

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

💡 Swapping will place 2 correctly and continue sorting.

swap

Swap nums[i] and nums[correct_index] again

Swap nums[0] and nums[1], placing 2 at index 1 and 1 at index 0.

💡 This swap places 2 correctly and brings 1 to be checked next.

Line:

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

💡 After this swap, nums[i] = 1, which might be correctly placed.

compare

Calculate correct index for nums[i] = 1

Now nums[i] = 1 at index 0, so correct_index = 0. Since nums[i] == nums[correct_index], no swap needed.

💡 When the number is already at its correct index, we move to the next index.

Line:

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

💡 No swap needed; increment i to process next element.

compare

Check if swap needed at i=1

At i=1, nums[i] = 2, correct_index = 1. Since nums[i] == nums[correct_index], increment i.

💡 Number 2 is correctly placed, so we move forward.

Line:

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

💡 Correctly placed numbers are skipped quickly.

compare

Check if swap needed at i=2

At i=2, nums[i] = 3, correct_index = 2. Since nums[i] == nums[correct_index], increment i.

💡 Number 3 is correctly placed, so we move forward.

Line:

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

💡 Correct placement confirmed for index 2.

compare

Calculate correct index for nums[i] = 5

At i=3, nums[i] = 5, so correct_index = 4. Check if swap needed with nums[4] = 3.

💡 We try to place 5 at index 4, but nums[4] is 3, so swap is needed.

Line:

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

💡 Swapping will move 5 to its correct position.

swap

Swap nums[i] and nums[correct_index]

Swap nums[3] and nums[4], placing 5 at index 4 and 3 at index 3.

💡 This swap moves 5 to its correct position and brings 3 to index 3 for further checking.

Line:

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

💡 After swap, nums[i] = 3, which may need further processing.

compare

Check if swap needed at i=3 again

At i=3, nums[i] = 3, correct_index = 2. Since nums[i] == nums[correct_index], no swap; increment i.

💡 Duplicate detected because the number is equal to the number at its target index.

Line:

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

💡 Duplicate number found at index 3; move forward to finish sorting.

compare

Check if swap needed at i=4

At i=4, nums[i] = 5, correct_index = 4. Since nums[i] == nums[correct_index], increment i to end loop.

💡 Number 5 is correctly placed at the last index.

Line:

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

💡 All numbers are now either correctly placed or duplicates handled.

traverse

Traverse array to find mismatch

Start scanning from i=0 to find the first index where nums[i] != i + 1.

💡 Mismatch indicates the duplicate and missing numbers.

Line:

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

💡 We look for the first incorrect placement after sorting.

compare

Check nums[0] == 1?

At i=0, nums[0] = 1 matches i+1 = 1, continue scanning.

💡 No mismatch here, so no duplicate or missing found yet.

Line:

if nums[i] != i + 1:

💡 Correct placement at index 0.

compare

Check nums[1] == 2?

At i=1, nums[1] = 2 matches i+1 = 2, continue scanning.

💡 Still no mismatch found.

Line:

if nums[i] != i + 1:

💡 Correct placement at index 1.

compare

Check nums[2] == 3?

At i=2, nums[2] = 3 matches i+1 = 3, continue scanning.

💡 Still no mismatch found.

Line:

if nums[i] != i + 1:

💡 Correct placement at index 2.

compare

Detect mismatch at i=3

At i=3, nums[3] = 3 does not equal i+1 = 4, so duplicate is 3 and missing is 4.

💡 Mismatch reveals the duplicate and missing numbers directly.

Line:

if nums[i] != i + 1:
    return [nums[i], i + 1]

💡 The duplicate number is the one at the mismatched index; the missing number is the expected value.

def find_duplicate_missing(nums):
    i = 0  # STEP 1
    n = len(nums)  # STEP 1
    while i < n:  # STEP 2-14
        correct_index = nums[i] - 1  # STEP 2,5,8,11
        if nums[i] != nums[correct_index]:  # STEP 3,6,9,12,13
            nums[i], nums[correct_index] = nums[correct_index], nums[i]  # STEP 4,7,12
        else:
            i += 1  # STEP 8,9,10,13,14
    for i in range(n):  # STEP 15-19
        if nums[i] != i + 1:  # STEP 15-19
            return [nums[i], i + 1]  # STEP 19
    return [-1, -1]

if __name__ == '__main__':
    print(find_duplicate_missing([3, 1, 2, 5, 3]))  # Output: [3, 4]

📊

Find Duplicate and Missing (Two Issues) - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer move reveals how cyclic sort organizes numbers and how the algorithm detects the duplicate and missing values without extra space.

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

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

move_right

1

0

2

1

i

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

swap

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

move_right

1

0

2

1

3

2

3

3

5

4

compare

i

1

0

2

1

3

2

3

3

5

4

compare

1

0

i

2

1

3

2

3

3

5

4

compare

1

0

2

1

i

3

2

3

3

5

4

compare

1

0

2

1

3

2

i

3

3

5

4

record

1

0

2

1

3

2

i

3

3

5

4

Result: [3,4]

Key Takeaways

✓ Cyclic sort places numbers at their correct indices by swapping, enabling detection of duplicates and missing numbers in one pass.

This insight is hard to see from code alone because the swapping logic and its effect on array order are subtle without visualization.

✓ When a number equals the number at its target index, it indicates either correct placement or a duplicate, which stops further swaps at that index.

Understanding this condition helps explain why the algorithm increments the pointer instead of swapping endlessly.

✓ The final scan for the first mismatch between index+1 and the number reveals both the duplicate and missing numbers simultaneously.

This step is elegant and non-obvious without seeing the array state after sorting.

Practice

1. Given the following code snippet implementing the cyclic sort approach, what is the returned output when the input array is [2, 2, 3]?

easy

A. [2, 1]

B. [2, 1]

C. [2, 1]

D. [2, 1]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [2, 2, 3]. i=0, nums[0]=2, correct_index=1. nums[0] == nums[1], so increment i to 1. i=1, nums[1]=2, correct_index=1, same index, increment i to 2. i=2, nums[2]=3, correct_index=2, correct place, increment i to 3.

2. Step 2: Identify mismatch in final array

   Final array remains [2, 2, 3]. Check indices: i=0 expects 1 but has 2 (duplicate), i=1 expects 2 and has 2 (correct), i=2 expects 3 and has 3 (correct). The mismatch at i=0 means duplicate=2, missing=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected corrupt pair [2, 1] [OK]

Hint: Trace swaps carefully; duplicates cause no swap but increment index [OK]

Common Mistakes:

• Off-by-one in indexing
• Returning wrong pair order
• Missing increment after swap

2. What is the time complexity of the optimal cyclic sort approach for finding all missing numbers in an array of size n, and why?

medium

A. O(n log n) because of the sorting-like swaps

B. O(n^2) because nested swaps can occur repeatedly for duplicates

C. O(n) because each element is swapped at most once to its correct position

D. O(n) but with O(n) auxiliary space for tracking swaps

Solution

1. Step 1: Analyze the while loop behavior

   Each number is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Confirm no nested repeated swaps

   Duplicates cause skipping increments but do not cause repeated swaps for the same element, so total operations remain linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to single pass and limited swaps [OK]

Hint: Each element swaps at most once [OK]

Common Mistakes:

• Assuming sorting cost O(n log n)
• Thinking duplicates cause quadratic swaps
• Confusing auxiliary space with time

3. What is the time complexity of the cyclic sort approach for finding the corrupt pair in an array of size n with one duplicate and one missing number?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n^2) because of nested loops swapping elements repeatedly

C. O(n) but with O(n) extra space for auxiliary arrays

D. O(n) because each element is swapped at most once

Solution

1. Step 1: Identify the main loop behavior

   The while loop runs with index i from 0 to n-1, but swaps only occur when elements are out of place, and each swap places at least one element correctly.

2. Step 2: Analyze swap count and increments

   Each element can be swapped at most once to its correct position, so total swaps ≤ n. The index increments ensure no infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time due to limited swaps and single pass [OK]

Hint: Each element swapped once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting inside algorithm
• Thinking swaps cause O(n^2)
• Confusing auxiliary space with time

4. What is the time complexity of the optimal cyclic sort approach for finding the smallest missing positive range in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n log n) because of the sorting-like swaps performed

B. O(n) because each element is swapped at most once to its correct position

C. O(n^2) because nested loops cause repeated scanning

D. O(n) but with O(n) auxiliary space due to recursion stack

Solution

1. Step 1: Analyze the swapping behavior

   Each element is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Understand loop iterations

   The outer while loop increments i only when no swap occurs, ensuring linear total iterations.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time due to bounded swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2)
• Confusing sorting complexity with cyclic sort

5. Suppose the input array can contain multiple duplicates and missing numbers (not just one pair). Which modification to the cyclic sort approach correctly finds all duplicate and missing numbers?

hard

A. Run the cyclic sort once and return the first mismatch found

B. Run cyclic sort, then scan entire array collecting all indices where nums[i] != i + 1

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

D. Sort the array and scan for duplicates and missing numbers in one pass

Solution

1. Step 1: Understand problem extension

   Multiple duplicates and missing numbers break the assumption of one-to-one mapping used in cyclic sort.

2. Step 2: Evaluate approaches

   Cyclic sort only detects one corrupt pair; frequency array counts all occurrences and identifies all duplicates and missing numbers reliably.

3. Step 3: Compare alternatives

   Sorting can find duplicates but is O(n log n) and less optimal; scanning after cyclic sort only finds first mismatch.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Frequency array handles multiple duplicates/missing efficiently [OK]

Hint: Cyclic sort assumes one duplicate; frequency array handles multiples [OK]

Common Mistakes:

• Assuming cyclic sort works for multiple duplicates
• Relying on first mismatch only
• Ignoring time-space tradeoffs