Find the Duplicate Number (Cyclic Sort)

▶

Steps

setup

Initialize pointers slow and fast

Set both slow and fast pointers to the first element's value, starting the cycle detection process.

💡 Initializing both pointers at the start ensures they traverse the array to detect the cycle caused by the duplicate.

Line:

slow = nums[0]
fast = nums[0]

💡 Both pointers start at the same position, ready to move through the array to find the cycle.

traverse

Move slow one step forward

Move slow pointer to the value at its current index (slow = nums[slow]).

💡 Moving slow by one step follows the linked structure of the array values.

Line:

slow = nums[slow]

💡 Slow pointer now points to the next index indicated by the current value.

traverse

Move fast two steps forward (first step)

Move fast pointer one step forward to the value at its current index (fast = nums[fast]).

💡 Fast pointer moves twice as fast, so this is the first of two moves.

Line:

fast = nums[fast]

💡 Fast pointer begins its two-step move by advancing one step.

traverse

Move fast two steps forward (second step)

Move fast pointer second step forward to the value at its current index (fast = nums[fast]).

💡 Completing fast pointer's two-step move helps detect cycle faster.

Line:

fast = nums[nums[fast]]

💡 Fast pointer now points two steps ahead, increasing chance to meet slow inside cycle.

compare

Check if slow equals fast (no match yet)

Compare slow and fast pointers to check if they meet inside the cycle.

💡 If slow equals fast, cycle detected; otherwise continue moving pointers.

Line:

if slow == fast:
    break

💡 Pointers have not met yet, so cycle detection continues.

traverse

Move slow one step forward

Advance slow pointer by one step to the value at its current index.

💡 Slow pointer continues moving stepwise to find cycle intersection.

Line:

slow = nums[slow]

💡 Slow pointer moves closer to the cycle intersection point.

traverse

Move fast two steps forward (first step)

Move fast pointer one step forward to the value at its current index.

💡 Fast pointer continues its two-step movement to catch slow pointer.

Line:

fast = nums[fast]

💡 Fast pointer moves closer to slow pointer inside the cycle.

traverse

Move fast two steps forward (second step)

Move fast pointer second step forward to the value at its current index.

💡 Completing fast pointer's two-step move to try meeting slow pointer.

Line:

fast = nums[nums[fast]]

💡 Fast pointer moves two steps ahead, potentially meeting slow pointer.

compare

Check if slow equals fast (no match yet)

Compare slow and fast pointers to check if they meet inside the cycle.

💡 Pointers must meet to confirm cycle; continue if not equal.

Line:

if slow == fast:
    break

💡 Pointers have not met yet; cycle detection continues.

traverse

Move slow one step forward

Advance slow pointer by one step to the value at its current index.

💡 Slow pointer moves closer to the cycle intersection point.

Line:

slow = nums[slow]

💡 Slow pointer moves to index 2.

traverse

Move fast two steps forward (first step)

Move fast pointer one step forward to the value at its current index.

💡 Fast pointer continues its two-step movement.

Line:

fast = nums[fast]

💡 Fast pointer moves to index 4.

traverse

Move fast two steps forward (second step)

Move fast pointer second step forward to the value at its current index.

💡 Completing fast pointer's two-step move.

Line:

fast = nums[nums[fast]]

💡 Fast pointer moves to index 2.

compare

Check if slow equals fast (pointers meet)

Slow and fast pointers meet at index 2, confirming cycle detection.

💡 Meeting point inside the cycle means duplicate detected.

Line:

if slow == fast:
    break

💡 Cycle detected; next phase is to find cycle entrance.

setup

Reset slow pointer to start

Reset slow pointer to the first element's value to find cycle entrance.

💡 Resetting slow prepares to find the duplicate number's index.

Line:

slow = nums[0]

💡 Slow pointer restarts from the beginning to locate cycle entrance.

traverse

Move slow and fast one step forward (slow)

Move slow pointer one step forward to the value at its current index.

💡 Slow pointer moves closer to cycle entrance.

Line:

slow = nums[slow]

💡 Slow pointer moves from index 1 to 3.

traverse

Move slow and fast one step forward (fast)

Move fast pointer one step forward to the value at its current index.

💡 Fast pointer moves one step to meet slow at cycle entrance.

Line:

fast = nums[fast]

💡 Fast pointer moves from index 2 to 4.

compare

Check if slow equals fast (no match yet)

Compare slow and fast pointers; they are not equal yet.

💡 Pointers must meet to find duplicate; continue moving.

Line:

while slow != fast:
    slow = nums[slow]
    fast = nums[fast]

💡 Pointers have not met; continue moving one step each.

traverse

Move slow one step forward

Move slow pointer one step forward to the value at its current index.

💡 Slow pointer moves closer to cycle entrance.

Line:

slow = nums[slow]

💡 Slow pointer moves from index 3 to 2.

traverse

Move fast one step forward

Move fast pointer one step forward to the value at its current index.

💡 Fast pointer moves to meet slow pointer at cycle entrance.

Line:

fast = nums[fast]

💡 Fast pointer moves from index 4 to 2.

compare

Pointers meet at duplicate number

Slow and fast pointers meet at index 2, which is the duplicate number.

💡 Meeting point is the entrance to the cycle and the duplicate number.

Line:

while slow != fast:
    slow = nums[slow]
    fast = nums[fast]
return slow

💡 Duplicate number found at the meeting point of pointers.

def findDuplicate(nums):
    slow = nums[0]  # STEP 1
    fast = nums[0]  # STEP 1
    while True:  # STEP 2-13 loop
        slow = nums[slow]  # STEP 2,6,10
        fast = nums[nums[fast]]  # STEP 3-4,7-8,11-12
        if slow == fast:  # STEP 5,9,13
            break
    slow = nums[0]  # STEP 14
    while slow != fast:  # STEP 15-20 loop
        slow = nums[slow]  # STEP 15,18
        fast = nums[fast]  # STEP 16,19
    return slow  # STEP 20

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

📊

Find the Duplicate Number (Cyclic Sort) - Watch the Algorithm Execute, Step by Step

Watching the pointers move and meet inside the cycle reveals how the algorithm detects duplicates without modifying the array or using extra space.

setup

fast

1

0

3

1

4

2

2

3

2

4

move_right

fast

1

0

slow

3

1

4

2

2

3

2

4

move_right

1

0

fast

3

1

4

2

2

3

2

4

move_right

1

0

slow

3

1

4

2

fast

2

3

2

4

compare

1

0

slow

3

1

4

2

fast

2

3

2

4

move_right

1

0

3

1

4

2

fast

2

3

2

4

move_right

1

0

3

1

fast

4

2

slow

2

3

2

4

move_right

1

0

3

1

fast

4

2

slow

2

3

2

4

compare

1

0

3

1

fast

4

2

slow

2

3

2

4

move_right

1

0

3

1

fast

4

2

2

3

2

4

move_right

1

0

3

1

slow

4

2

2

3

fast

2

4

move_right

1

0

3

1

fast

4

2

2

3

2

4

compare

1

0

3

1

fast

4

2

2

3

2

4

setup

1

0

slow

3

1

fast

4

2

2

3

2

4

move_right

1

0

3

1

fast

4

2

slow

2

3

2

4

move_right

1

0

3

1

4

2

slow

2

3

fast

2

4

compare

1

0

3

1

4

2

slow

2

3

fast

2

4

move_right

1

0

3

1

slow

4

2

2

3

fast

2

4

move_right

1

0

3

1

fast

4

2

2

3

2

4

record

1

0

3

1

fast

4

2

2

3

2

4

Result: 2

Key Takeaways

✓ Cycle detection via two pointers reveals duplicates without modifying the array.

This insight is hard to see from code alone because the pointers' movement and meeting point are abstract without visualization.

✓ Fast pointer moves twice as fast to guarantee meeting slow pointer inside the cycle.

Visualizing the two-step move clarifies why fast pointer catches slow pointer efficiently.

✓ Resetting slow pointer and moving both pointers one step at a time locates the cycle entrance, which is the duplicate.

Seeing the pointers converge at the duplicate index concretely explains the cycle entrance concept.

Practice

1. Given the following code snippet, what is the output when the input array is [3,1,2,2]?

easy

A. []

B. [3]

C. [1]

D. [2]

Solution

1. Step 1: Trace swaps in while loop

   Initial array: [3,1,2,2]. Swap nums[0] and nums[2]: [2,1,3,2]. Swap nums[0] and nums[1]: [1,2,3,2]. i increments to 1,2,3 without swaps.

2. Step 2: Identify duplicates in final array

   Final array: [1,2,3,2]. Index 3 has value 2 instead of 4, so duplicate is 2.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only 2 appears twice, correctly identified [OK]

Hint: Trace swaps carefully to find duplicates [OK]

Common Mistakes:

• Confusing index and value during swaps
• Missing the duplicate in final scan
• Off-by-one errors in final check

2. Consider the following code snippet implementing the cyclic sort approach to find the missing number:

def missingNumber(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i]
        if correct < n and nums[i] != nums[correct]:
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

print(missingNumber([3, 0, 1]))  # ?

What is the output of this code?

easy

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace the while loop swaps

   Initial array: [3,0,1] - i=0: nums[0]=3, 3 < 3? No, so i=1 - i=1: nums[1]=0, 0 < 3 and nums[1]!=nums[0], swap nums[1] and nums[0]: [0,3,1] - i=1 again: nums[1]=3, 3 < 3? No, i=2 - i=2: nums[2]=1, 1 < 3 and nums[2]!=nums[1], swap nums[2] and nums[1]: [0,1,3] - i=2 again: nums[2]=3, 3 < 3? No, i=3 (exit loop)

2. Step 2: Scan for mismatch

   Check indices: - i=0: nums[0]=0 correct - i=1: nums[1]=1 correct - i=2: nums[2]=3 != 2 -> missing number is 2

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected missing number 2 [OK]

Hint: Swapping places numbers at their indices [OK]

Common Mistakes:

• Returning the last index instead of missing number
• Off-by-one errors in loop increments
• Confusing swapped values

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. Consider this buggy code snippet for finding missing numbers. Which line contains the subtle bug that can cause infinite loops or incorrect output?

medium

A. Line 3: wrong initialization of n

B. Line 7: incorrect increment of i

C. Line 9: appending missing numbers incorrectly

D. Line 5: missing check before swapping

Solution

1. Step 1: Identify the missing condition before swap

   The code swaps unconditionally without checking if nums[i] == nums[correct], causing infinite swaps when duplicates exist.

2. Step 2: Confirm other lines are correct

   Incrementing i only happens in else, missing numbers appended correctly, and n initialized properly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing condition before swap causes infinite loop or wrong placement [OK]

Hint: Check swap condition to avoid infinite loops [OK]

Common Mistakes:

• Forgetting duplicate check before swap
• Incrementing i incorrectly
• Appending indices instead of values

5. Consider the following buggy implementation of the cyclic sort approach to find the smallest missing positive range. Identify the line that contains the subtle bug causing incorrect results or infinite loops.

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
            # Missing increment of i here
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

medium

A. Line missing increment of i after swap inside the while loop

B. Line with the swap: nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

C. Line checking if nums[i] != i + 1 in the for loop

D. Line returning [n + 1, n + 1] if no missing range found

Solution

1. Step 1: Identify the infinite loop cause

   After swapping, the index i is not incremented, so the same index is checked repeatedly causing infinite loop.

2. Step 2: Confirm other lines are correct

   Swap line correctly swaps elements; the for loop and return lines handle missing range detection properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing i increment after swap causes infinite loop or incorrect behavior [OK]

Hint: Always increment index after swap or carefully control loop [OK]

Common Mistakes:

• Forgetting to increment i after swap
• Misplacing swap condition