Find the Duplicate Number (Floyd on Array)

▶

Steps

setup

Initialize slow and fast pointers

Both slow and fast pointers start at the first element of the array, which is the value at index 0.

💡 Starting both pointers at the same position sets up the initial state for cycle detection.

Line:

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

💡 Both pointers begin at the same index, ready to traverse the array to detect a cycle.

compare

Move slow pointer one step

Move slow pointer from index 1 to the value at nums[1], which is 3.

💡 Slow pointer moves one step to follow the chain of indices.

Line:

slow = nums[slow]

💡 Slow pointer now points to index 3, advancing one step in the cycle detection.

compare

Move fast pointer two steps

Move fast pointer two steps: first to nums[1] = 3, then to nums[3] = 2.

💡 Fast pointer moves twice as fast to detect cycle quicker.

Line:

fast = nums[nums[fast]]

💡 Fast pointer jumps ahead to index 2, moving two steps in one operation.

compare

Move slow pointer one step

Move slow pointer from index 3 to nums[3] = 2.

💡 Slow pointer continues moving one step at a time.

Line:

slow = nums[slow]

💡 Slow pointer now points to index 2, closing in on the cycle.

compare

Check if slow equals fast

Both pointers are at index 2, so they meet inside the cycle.

💡 Meeting point confirms a cycle exists in the array.

Line:

if slow == fast:
    break

💡 Cycle detected; now we find the cycle’s entry point.

setup

Reset slow pointer to start

Reset slow pointer to the first element of the array (index 1). Fast pointer remains at meeting point.

💡 Resetting slow prepares to find the cycle entry point by moving both pointers at same speed.

Line:

slow = nums[0]

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

traverse

Move slow pointer one step

Move slow pointer from index 1 to nums[1] = 3.

💡 Both pointers now move one step at a time to find the cycle entry.

Line:

slow = nums[slow]

💡 Slow pointer advances to index 3, moving closer to the duplicate.

traverse

Move fast pointer one step

Move fast pointer from index 2 to nums[2] = 4.

💡 Fast pointer moves one step to keep pace with slow pointer.

Line:

fast = nums[fast]

💡 Fast pointer advances to index 4, continuing the search for cycle entry.

traverse

Move slow pointer one step

Move slow pointer from index 3 to nums[3] = 2.

💡 Slow pointer continues moving one step closer to the cycle entry.

Line:

slow = nums[slow]

💡 Slow pointer now points to index 2, nearing the duplicate number.

traverse

Move fast pointer one step

Move fast pointer from index 4 to nums[4] = 2.

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

Line:

fast = nums[fast]

💡 Fast pointer now points to index 2, the cycle entry and duplicate number.

reconstruct

Return the duplicate number

Since slow and fast pointers meet at index 2, return this as the duplicate number.

💡 The meeting point of pointers is the duplicate number in the array.

Line:

return slow

💡 The cycle entry corresponds to the duplicate number, which is the final answer.

def findDuplicate(nums):
    slow = nums[0]  # STEP 1
    fast = nums[0]  # STEP 1
    # Phase 1: Find intersection point
    while True:
        slow = nums[slow]  # STEP 2,4
        fast = nums[nums[fast]]  # STEP 3
        if slow == fast:  # STEP 5
            break
    # Phase 2: Find entrance to cycle
    slow = nums[0]  # STEP 6
    while slow != fast:
        slow = nums[slow]  # STEP 7,9
        fast = nums[fast]  # STEP 8,10
    return slow  # STEP 11

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

📊

Find the Duplicate Number (Floyd on Array) - Watch the Algorithm Execute, Step by Step

Watching the pointers move step-by-step reveals how the cycle detection algorithm works internally, making the abstract concept concrete and easier to grasp.

setup

1

0

fast

3

1

4

2

2

3

2

4

move_right

1

0

fast

3

1

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

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

move_right

1

0

3

1

slow

4

2

2

3

fast

2

4

compare

1

0

3

1

fast

4

2

2

3

2

4

Result: 2

record

1

0

3

1

fast

4

2

2

3

2

4

Result: 2

Key Takeaways

✓ The duplicate number creates a cycle in the array when viewed as pointers to indices.

This insight is hard to see from code alone because the array values are used as indices, which is a non-obvious transformation.

✓ The fast pointer moves twice as fast as the slow pointer to detect the cycle efficiently.

Visualizing the two pointers moving at different speeds clarifies why the cycle detection works and how they eventually meet.

✓ Resetting the slow pointer to the start and moving both pointers one step at a time finds the cycle entry, which is the duplicate number.

This step is subtle in code but clear in visualization, showing how the meeting point after reset reveals the duplicate.

Practice

1. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

2. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

3. What is the time and space complexity of Floyd's cycle detection algorithm used to find the start of a cycle in a linked list of length n?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(n log n), Space: O(1)

Solution

1. Step 1: Analyze time complexity of pointer movements

   Fast pointer moves twice as fast as slow pointer, so they meet in O(n) steps, and locating cycle start also takes O(n) steps, total O(n).

2. Step 2: Analyze space complexity

   Only a fixed number of pointers are used, no extra data structures, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space are standard for Floyd's algorithm [OK]

Hint: Two pointers traverse list linearly, no extra space needed [OK]

Common Mistakes:

• Confusing space with hash set approach
• Assuming quadratic time due to nested loops
• Mistaking recursion stack space

4. The following code attempts to remove the nth node from the end of a singly linked list. Identify the line containing the subtle bug that causes incorrect behavior when removing the head node.

medium

A. Line 12: recurse(head)

B. Line 9: node.next = node.next.next

C. Line 3: def recurse(node):

D. Line 13: return head

Solution

1. Step 1: Understand dummy node role

   Dummy node is needed to handle removal of the head node safely.

2. Step 2: Identify missing dummy usage

   Calling recurse on head directly skips dummy, so removing head node breaks list or returns wrong head.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dummy node causes incorrect removal of head [OK]

Hint: Always use dummy node to handle head removal edge case [OK]

Common Mistakes:

• Not using dummy node causing null pointer or wrong head
• Incorrectly unlinking nodes causing list corruption
• Off-by-one errors in recursion index

5. Suppose the problem is modified so that after deleting N nodes, the deleted nodes can be reinserted later in the list (i.e., nodes can be reused). Which of the following changes to the algorithm is necessary to correctly handle this variant?

hard

A. Use a recursive approach to backtrack and reinsert deleted nodes at correct positions.

B. Maintain a separate data structure to store deleted nodes and reinsert them after traversal.

C. Modify the iterative approach to skip M nodes, delete N nodes, and immediately reattach deleted nodes after the next M nodes.

D. No change needed; the original iterative approach already supports node reuse.

Solution

1. Step 1: Understand node reuse requirement

   Deleted nodes must be preserved and reinserted later, so they cannot be simply discarded by pointer reassignment.

2. Step 2: Evaluate algorithm changes

   The original approach loses references to deleted nodes. To reuse, store deleted nodes externally and reinsert after traversal or at correct positions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maintaining deleted nodes separately enables controlled reinsertion [OK]

Hint: Reusing nodes requires storing them, not discarding pointers [OK]

Common Mistakes:

• Assuming original approach supports reuse
• Trying to reattach nodes immediately without storage
• Using recursion unnecessarily