Find Cycle in Array (Jump Game)

▶

Steps

setup

Initialize variables and start first iteration

Set up the array and prepare to iterate over each index as a potential cycle start point. The first index to check is 0.

💡 Starting from each index ensures we check all possible cycles in the array.

Line:

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

💡 We must consider every index as a potential cycle start to avoid missing cycles.

setup

Check if current start index is already visited

Check if nums[0] is zero, which would mean this index was already visited and skipped. Since nums[0] = 2, continue.

💡 Skipping zero values avoids redundant work on already processed indices.

Line:

if nums[i] == 0:
    continue

💡 Only unvisited indices are considered as cycle start points.

setup

Initialize slow and fast pointers and direction

Set slow and fast pointers to start index 0. Determine direction as positive since nums[0] = 2 > 0.

💡 Direction consistency is crucial to detect valid cycles without direction changes.

Line:

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

💡 Both pointers start at the same index and direction guides allowed moves.

traverse

Calculate next index for slow pointer

Move slow pointer one step forward: slow_next = (0 + nums[0]) % 5 = 2.

💡 Slow pointer moves one step to explore the sequence.

Line:

slow_next = next_index(slow)

💡 The slow pointer follows the jump defined by the current node's value.

traverse

Calculate next index for fast pointer (first jump)

Move fast pointer one step forward: fast_next = (0 + nums[0]) % 5 = 2.

💡 Fast pointer moves twice as fast, so we calculate two jumps per iteration.

Line:

fast_next = next_index(fast)

💡 First jump of fast pointer matches slow pointer's next position.

compare

Check direction consistency for slow_next and fast_next

Verify if nums[slow_next] and nums[fast_next] have the same direction as initial. Both nums[2]=1 and nums[2]=1 are positive, matching direction.

💡 Direction consistency ensures cycle is valid and not mixed with opposite jumps.

Line:

if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:
    break

💡 Direction check prevents false cycles caused by direction changes.

traverse

Calculate second jump for fast pointer

Move fast pointer one more step: fast_next = next_index(2) = (2 + nums[2]) % 5 = (2 + 1) % 5 = 3.

💡 Fast pointer moves two steps per iteration to detect cycles faster.

Line:

fast_next = next_index(fast_next)

💡 Fast pointer's second jump advances it further ahead in the sequence.

compare

Check direction consistency for fast pointer's second jump

Check if nums[fast_next] = nums[3] = 2 is positive and matches direction. It does, so continue.

💡 Each jump must maintain direction to be part of a valid cycle.

Line:

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

💡 Direction check after second jump ensures cycle validity.

traverse

Advance slow and fast pointers

Update slow to slow_next (2) and fast to fast_next (3) to continue cycle detection.

💡 Pointers move forward to explore the sequence and detect cycles.

Line:

slow, fast = slow_next, fast_next

💡 Pointers progress through the array according to jump rules.

traverse

Calculate next index for slow pointer

Move slow pointer one step forward: slow_next = (2 + nums[2]) % 5 = (2 + 1) % 5 = 3.

💡 Slow pointer continues to move one step at a time.

Line:

slow_next = next_index(slow)

💡 Slow pointer follows the jump from its current position.

traverse

Calculate next index for fast pointer (first jump)

Move fast pointer one step forward: fast_next = (3 + nums[3]) % 5 = (3 + 2) % 5 = 0.

💡 Fast pointer continues its first jump in this iteration.

Line:

fast_next = next_index(fast)

💡 Fast pointer moves according to the jump value at its current index.

compare

Check direction consistency for slow_next and fast_next

Check if nums[slow_next] = nums[3] = 2 and nums[fast_next] = nums[0] = 2 are positive and match direction. Both do, so continue.

💡 Direction consistency is checked again to ensure valid cycle traversal.

Line:

if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:
    break

💡 Maintaining direction consistency is key to valid cycle detection.

traverse

Calculate second jump for fast pointer

Move fast pointer one more step: fast_next = next_index(0) = (0 + nums[0]) % 5 = 2.

💡 Fast pointer completes its second jump for this iteration.

Line:

fast_next = next_index(fast_next)

💡 Fast pointer moves ahead quickly to detect cycles efficiently.

compare

Check direction consistency for fast pointer's second jump

Check if nums[fast_next] = nums[2] = 1 is positive and matches direction. It does, so continue.

💡 Direction check after second jump ensures cycle validity.

Line:

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

💡 Direction consistency is maintained throughout traversal.

traverse

Advance slow and fast pointers

Update slow to slow_next (3) and fast to fast_next (2) to continue cycle detection.

💡 Pointers move forward to explore the sequence and detect cycles.

Line:

slow, fast = slow_next, fast_next

💡 Pointers progress through the array according to jump rules.

traverse

Calculate next index for slow pointer

Move slow pointer one step forward: slow_next = (3 + nums[3]) % 5 = (3 + 2) % 5 = 0.

💡 Slow pointer continues to move one step at a time.

Line:

slow_next = next_index(slow)

💡 Slow pointer follows the jump from its current position.

traverse

Calculate next index for fast pointer (first jump)

Move fast pointer one step forward: fast_next = (2 + nums[2]) % 5 = (2 + 1) % 5 = 3.

💡 Fast pointer continues its first jump in this iteration.

Line:

fast_next = next_index(fast)

💡 Fast pointer moves according to the jump value at its current index.

compare

Check direction consistency for slow_next and fast_next

Check if nums[slow_next] = nums[0] = 2 and nums[fast_next] = nums[3] = 2 are positive and match direction. Both do, so continue.

💡 Direction consistency is checked again to ensure valid cycle traversal.

Line:

if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:
    break

💡 Maintaining direction consistency is key to valid cycle detection.

traverse

Calculate second jump for fast pointer

Move fast pointer one more step: fast_next = next_index(3) = (3 + nums[3]) % 5 = (3 + 2) % 5 = 0.

💡 Fast pointer completes its second jump for this iteration.

Line:

fast_next = next_index(fast_next)

💡 Fast pointer moves ahead quickly to detect cycles efficiently.

compare

Pointers meet: cycle detected

Update slow and fast pointers: slow = slow_next = 0, fast = fast_next = 0. Since slow == fast and slow != next_index(slow), a cycle is detected and algorithm returns true.

💡 When slow and fast pointers meet at a node other than a self-loop, a cycle exists.

Line:

slow, fast = slow_next, fast_next
if slow == fast:
    if slow == next_index(slow):
        break
    return True

💡 Meeting pointers confirm a cycle in the array jumps.

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-2
        if nums[i] == 0:  # STEP 2
            continue
        slow, fast = i, i  # STEP 3
        direction = nums[i] > 0  # STEP 3
        while True:
            slow_next = next_index(slow)  # STEP 4,10,16
            fast_next = next_index(fast)  # STEP 5,11,17
            if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:  # STEP 6,12,18
                break
            fast_next = next_index(fast_next)  # STEP 7,13,19
            if (nums[fast_next] > 0) != direction:  # STEP 8,14,20
                break
            slow, fast = slow_next, fast_next  # STEP 9,15,20
            if slow == fast:  # STEP 20
                if slow == next_index(slow):  # STEP 20
                    break
                return True  # STEP 20
        marker = i  # Not reached in this example
        while nums[marker] != 0 and (nums[marker] > 0) == direction:
            next_marker = next_index(marker)
            nums[marker] = 0
            marker = next_marker
    return False

if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True

📊

Find Cycle in Array (Jump Game) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and decision helps you understand how cycle detection works on implicit sequences without explicit graph structures.

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

advance

2

→

-1

→

1

→

2

→

2

compare

2

→

-1

→

1

→

2

→

2

Result: true

Key Takeaways

✓ Fast and slow pointers moving at different speeds detect cycles efficiently in implicit sequences.

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

✓ Direction consistency checks prevent false positives by ensuring cycles are formed by jumps in the same direction.

Understanding why direction matters is easier when you see the algorithm break early on direction changes.

✓ When slow and fast pointers meet at a node that is not a self-loop, a valid cycle is confirmed.

Visualizing pointer meeting clarifies the cycle detection condition beyond just reading the equality check in code.

Practice

1. Consider the following code that detects a cycle by marking nodes as visited. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2), what is the output of hasCycle(node1)?

easy

A. true

B. false

C. null

D. Runtime error due to infinite loop

Solution

1. Step 1: Trace the traversal and marking of nodes

   Start at node1 (visited=false), mark visited=true, move to node2. Repeat for node2 and node3. When reaching node4, mark visited=true and move to node2 again, which is already visited.

2. Step 2: Detect cycle when revisiting node2

   Since node2.visited is true, the function returns true indicating a cycle.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detected correctly by visited flag [OK]

Hint: Cycle detected when revisiting a marked node [OK]

Common Mistakes:

• Assuming no cycle due to missing pointer update
• Confusing return values

2. Consider the following code snippet for detecting and returning the length of a cycle in a linked list. Given the linked list: 3 -> 2 -> 0 -> -4 -> (back to node with value 2), what is the returned cycle length?

easy

A. 2

B. 3

C. 4

D. 0

Solution

1. Step 1: Trace fast and slow pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet at node with value 2 after some iterations.

2. Step 2: Count cycle length by moving slow pointer until it meets fast again

   Starting from node 2, slow moves through nodes 0, -4, then back to 2, counting 3 nodes total.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Cycle length is nodes 2 -> 0 -> -4 -> back to 2 = 3 [OK]

Hint: Cycle length equals number of unique nodes in loop [OK]

Common Mistakes:

• Off-by-one counting cycle length
• Confusing meeting point with cycle start
• Returning 0 when cycle exists

3. You are given a singly linked list and an integer n. The task is to remove the n-th node from the end of the list in a single pass without using extra space for storing nodes. Which approach guarantees this optimal solution?

easy

A. Traverse the list twice: first to count nodes, second to remove the target node.

B. Sort the list first, then remove the node at position length - n.

C. Use two pointers with a fixed gap of n+1 nodes, moving together until the fast pointer reaches the end.

D. Use a dynamic programming approach to store intermediate results for each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires removing the n-th node from the end in one pass without extra storage.

2. Step 2: Identify the two-pointer technique for single-pass removal

   Using two pointers with a gap of n+1 nodes ensures the slow pointer stops just before the target node, allowing removal in one pass.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n+1 enable single-pass removal [OK]

Common Mistakes:

• Using two passes instead of one
• Trying to sort the list which is unnecessary
• Confusing DP with linked list traversal

4. What is the time complexity of the optimized fast and slow pointer approach for detecting a circular array loop in an array of length n?

medium

A. O(n^2) because each element may be visited multiple times

B. O(n log n) due to repeated modulo operations and pointer jumps

C. O(n) because each element is visited at most once due to marking visited elements

D. O(n) amortized but worst case can be O(n^2) if cycles overlap

Solution

1. Step 1: Identify outer loop and inner pointer movements

   The outer loop runs n times, but elements are marked zero once visited, preventing reprocessing.

2. Step 2: Analyze pointer visits

   Each element is visited at most once in the inner while loop due to zero marking, so total work is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Marking visited elements ensures linear time complexity [OK]

Hint: Marking visited elements prevents repeated work -> O(n) [OK]

Common Mistakes:

• Assuming repeated visits cause O(n^2)
• Confusing modulo cost as log factor
• Believing overlapping cycles increase complexity

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily