Circular Array Loop

▶

Steps

setup

Initialize variables and start first iteration

Set up the array and prepare to iterate over each index to find cycles. Start with index 0 as the first candidate.

💡 Initialization sets the stage for the algorithm to explore each index systematically.

Line:

n = len(nums)
for i in range(n):

💡 The algorithm will check each index unless it is already marked visited (0).

compare

Check if current index is visited

Check if nums[0] is zero, which would mean it is already visited and should be skipped. It is not zero, so proceed.

💡 Skipping visited indices avoids redundant work and infinite loops.

Line:

if nums[i] == 0:
    continue

💡 Index 0 is a valid starting point for cycle detection.

setup

Set direction and initialize slow and fast pointers

Determine the direction of movement from index 0 (positive). Initialize slow and fast pointers both at index 0.

💡 Direction consistency is crucial to detect valid cycles moving all forward or all backward.

Line:

direction = nums[i] > 0
slow, fast = i, i

💡 Both pointers start at the same index to begin cycle detection.

traverse

Move slow pointer one step

Move slow pointer from index 0 to next index calculated by (0 + nums[0]) % 5 = 2.

💡 Slow pointer moves one step to explore the path for cycle detection.

Line:

slow = next_index(slow)

💡 Slow pointer advances to index 2.

traverse

Move fast pointer two steps

Move fast pointer two steps: first from 0 to 2, then from 2 to 3.

💡 Fast pointer moves twice as fast to detect cycles efficiently.

Line:

fast = next_index(next_index(fast))

💡 Fast pointer advances to index 3.

compare

Check direction consistency for slow pointer

Check if nums[slow] (nums[2] = 1) has the same direction as initial (positive). It does, so continue.

💡 Direction consistency ensures the cycle moves all forward or all backward.

Line:

if (nums[slow] > 0) != direction:
    break

💡 Slow pointer's position is valid for cycle detection.

compare

Check direction consistency for fast pointer

Check if nums[fast] (nums[3] = 2) has the same direction as initial (positive). It does, so continue.

💡 Both pointers must move in the same direction to confirm a valid cycle.

Line:

if (nums[fast] > 0) != direction:
    break

💡 Fast pointer's position is valid for cycle detection.

compare

Check if slow and fast pointers meet

Check if slow and fast pointers are at the same index. They are not (2 != 3), so continue the loop.

💡 Pointers meeting indicates a cycle; otherwise, continue searching.

Line:

if slow == fast:

💡 No cycle detected yet, pointers continue moving.

traverse

Move slow pointer one step

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

💡 Slow pointer advances to catch up with fast pointer.

Line:

slow = next_index(slow)

💡 Slow pointer now at index 3.

traverse

Move fast pointer two steps

Move fast pointer two steps: from 3 to 0, then from 0 to 2.

💡 Fast pointer continues moving quickly to detect cycle.

Line:

fast = next_index(next_index(fast))

💡 Fast pointer now at index 2.

compare

Check direction consistency for slow pointer

Check if nums[slow] (nums[3] = 2) matches direction (positive). It does, continue.

💡 Direction consistency check prevents invalid cycles.

Line:

if (nums[slow] > 0) != direction:
    break

💡 Slow pointer position valid.

compare

Check direction consistency for fast pointer

Check if nums[fast] (nums[2] = 1) matches direction (positive). It does, continue.

💡 Both pointers must maintain direction consistency.

Line:

if (nums[fast] > 0) != direction:
    break

💡 Fast pointer position valid.

compare

Check if slow and fast pointers meet

Pointers are at different indices (3 != 2), so continue the loop.

💡 Cycle detection requires pointers to meet.

Line:

if slow == fast:

💡 No cycle detected yet.

traverse

Move slow pointer one step

Move slow pointer from 3 to 0 (3 + nums[3] = 0).

💡 Slow pointer advances to continue cycle detection.

Line:

slow = next_index(slow)

💡 Slow pointer now at index 0.

traverse

Move fast pointer two steps

Move fast pointer two steps: from 2 to 3, then from 3 to 0.

💡 Fast pointer moves quickly to catch slow pointer.

Line:

fast = next_index(next_index(fast))

💡 Fast pointer now at index 0.

compare

Check if slow and fast pointers meet

Slow and fast pointers both point to index 0, indicating a cycle.

💡 Pointer collision confirms a cycle in the array.

Line:

if slow == fast:

💡 Cycle detected at index 0.

compare

Check for single-element loop

Check if the cycle is a single-element loop by comparing slow to next_index(slow). It is not (0 != 2), so valid cycle.

💡 Single-element loops are invalid cycles and must be ignored.

Line:

if slow == next_index(slow):
    break

💡 Cycle involves multiple elements.

prune

Return true due to cycle detection

Since a valid cycle is found, the function returns true immediately, ending the search.

💡 Early exit optimizes performance by stopping once a cycle is found.

Line:

return True

💡 Cycle detection is complete and successful.

def circularArrayLoop(nums):
    n = len(nums)  # STEP 1
    def next_index(i):  # STEP 1
        return (i + nums[i]) % n

    for i in range(n):  # STEP 1
        if nums[i] == 0:  # STEP 2
            continue
        direction = nums[i] > 0  # STEP 3
        slow, fast = i, i  # STEP 3
        while True:
            slow = next_index(slow)  # STEP 4,9,14
            fast = next_index(next_index(fast))  # STEP 5,10,15
            if (nums[slow] > 0) != direction:  # STEP 6,11
                break
            if (nums[fast] > 0) != direction:  # STEP 7,12
                break
            if slow == fast:  # STEP 8,13,16
                if slow == next_index(slow):  # STEP 17
                    break
                return True  # STEP 18
        slow = i
        while (nums[slow] > 0) == direction:
            next_i = next_index(slow)
            nums[slow] = 0
            slow = next_i
    return False

📊

Circular Array Loop - Watch the Algorithm Execute, Step by Step

Watching each pointer move and decision in real-time reveals how cycle detection works in a circular array, making the abstract logic concrete and intuitive.

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

setup

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

Result: true

compare

2

→

-1

→

1

→

2

→

2

Result: true

prune

2

→

-1

→

1

→

2

→

2

Result: true

Key Takeaways

✓ Fast and slow pointers moving at different speeds can detect cycles efficiently in a circular array.

This insight is hard to see from code alone because the pointer movements and their interaction are abstract without visualization.

✓ Direction consistency checks ensure that cycles are valid by requiring all moves to be forward or all backward.

Visualizing direction checks clarifies why mixed directions break the cycle detection early.

✓ Early exit upon detecting a cycle improves performance by avoiding unnecessary traversal.

Seeing the algorithm stop immediately after cycle detection helps understand the optimization.

Practice

1. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

2. Consider the following buggy code for finding the middle node of a linked list. Which line contains the subtle bug that can cause a runtime error?

medium

A. Line 4: while fast.next and fast.next.next:

B. Line 3: fast = head

C. Line 2: slow = head

D. Line 6: return slow

Solution

1. Step 1: Analyze loop condition

   The condition checks fast.next and fast.next.next but does not check if fast itself is null, which can cause AttributeError if fast is null.

2. Step 2: Identify fix

   Change condition to while fast and fast.next to safely access fast.next.next.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing fast null check causes runtime error on short lists [OK]

Hint: Always check fast pointer is not null before accessing next [OK]

Common Mistakes:

• Assuming fast.next is safe without checking fast
• Returning first middle node incorrectly
• Modifying list nodes accidentally

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

4. Suppose the array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods

5. Suppose the linked list nodes can be reused multiple times in cycles (i.e., cycles can overlap or nest). Which modification to the fast-slow pointer approach correctly detects and counts the length of the first cycle encountered?

hard

A. Use a hash set to track visited nodes to detect cycles and count length, since fast-slow pointers fail with overlapping cycles.

B. Modify the fast pointer to move three steps at a time to detect overlapping cycles faster.

C. Run the fast-slow pointer detection multiple times from different starting points to find all cycles.

D. Use fast-slow pointers as usual; overlapping cycles do not affect detection of the first cycle.

Solution

1. Step 1: Understand overlapping cycles scenario

   Overlapping or nested cycles mean fast-slow pointers may not reliably detect all cycles or count lengths correctly.

2. Step 2: Evaluate approaches for correctness

   Using a hash set tracks all visited nodes, ensuring detection of any cycle and accurate length counting despite overlaps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set approach handles complex cycle structures correctly [OK]

Hint: Fast-slow pointers detect only simple cycles reliably [OK]

Common Mistakes:

• Assuming fast-slow pointers handle overlapping cycles
• Increasing fast pointer speed breaks correctness
• Multiple runs of fast-slow pointers are inefficient and incomplete