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 circular array where each element represents a jump length and direction (positive for forward, negative for backward). The task is to determine if there exists a cycle in the array such that the cycle is longer than one element and all jumps are in the same direction. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to jump as far as possible from each index until a cycle is detected or no progress is made.

B. Dynamic programming to store reachable indices and detect cycles by memoization.

C. Brute force simulation from each index checking all possible cycles exhaustively.

D. Fast and slow pointer cycle detection that checks direction consistency and avoids single-element loops.

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify suitable algorithm

   Fast and slow pointer cycle detection efficiently finds cycles in O(n) time while checking direction and cycle length constraints.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast and slow pointers detect cycles without exhaustive search [OK]

Hint: Cycle detection with direction check -> fast-slow pointers [OK]

Common Mistakes:

• Assuming greedy jumps always find cycles
• Using DP which is inefficient here
• Brute force is correct but not optimal

2. Consider the following Python code that removes the 2nd node from the end of the list 1 -> 2 -> 3 -> 4 -> 5. What is the printed output after execution?

easy

A. 1 2 4 5

B. 1 2 3 5

C. 1 3 4 5

D. 2 3 4 5

Solution

1. Step 1: Trace recursion from end

   Recursion returns indices from the end: node 5 returns 1, node 4 returns 2, node 3 returns 3, etc.

2. Step 2: Identify node to remove

   When idx == n+1 = 3, node 3's next pointer skips node 4, effectively removing node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches list with 4 removed: 1 2 3 5 [OK]

Hint: Recursion index counts from end; remove node at idx = n+1 [OK]

Common Mistakes:

• Removing the node at idx == n instead of n+1
• Off-by-one errors in recursion index
• Confusing which node to skip

3. You are given a singly linked list and an integer k. The task is to split the list into k consecutive parts such that the sizes of the parts differ by at most one, and the earlier parts are larger if sizes differ. Which algorithmic approach best guarantees an optimal solution with minimal passes over the list?

easy

A. Greedy approach that assigns nodes to parts until each part reaches an average size, without pre-counting total nodes.

B. Dynamic programming to find the optimal partition minimizing size differences between parts.

C. Repeatedly remove nodes from the front and append to parts until all nodes are distributed, without precomputing sizes.

D. Calculate total nodes first, then split the list in one pass using precomputed part sizes and carefully breaking links.

Solution

1. Step 1: Understand problem constraints

   The problem requires splitting into k parts with sizes differing by at most one, favoring earlier parts to be larger.

2. Step 2: Identify approach that meets constraints efficiently

   Calculating total nodes first allows precise part sizes and a single pass to split, ensuring correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Precomputing sizes avoids guesswork and multiple passes [OK]

Hint: Precompute total nodes to split correctly in one pass [OK]

Common Mistakes:

• Assuming greedy without counting nodes works
• Trying DP unnecessarily
• Splitting without breaking links properly

4. Examine the following buggy code snippet for deleting N nodes after skipping M nodes in a linked list. Identify the line that contains the subtle bug causing potential runtime errors or incorrect output.

def delete_n_after_m_buggy(head, M, N):
    current = head
    while current:
        for _ in range(1, M):
            current = current.next
        if current is null:
            break
        temp = current.next
        for _ in range(N):
            if temp is null:
                break
            temp = temp.next
        current.next = temp
        current = temp
    return head

medium

A. Line 13: current.next = temp

B. Line 6: if current is null: break

C. Line 10: for _ in range(N): if temp is null: break

D. Line 4: for _ in range(1, M): current = current.next

Solution

1. Step 1: Analyze pointer movement in skipping loop

   The loop moves current forward M-1 times without checking if current is null before moving, risking NoneType attribute errors.

2. Step 2: Identify missing null check

   Without checking current before current = current.next, code may dereference null, causing runtime error.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding null check inside skipping loop prevents runtime errors [OK]

Hint: Always check for null before moving pointers in loops [OK]

Common Mistakes:

• Missing null checks before pointer moves
• Incorrectly updating next pointers causing cycles
• Assuming list length always sufficient

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