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. Given the following code, what is the output when calling nth_from_end(head, 3) where head is a linked list with values [5, 10, 15, 20]?

easy

A. 5

B. 15

C. 20

D. 10

Solution

1. Step 1: Trace stack contents after traversal

   Stack after pushing nodes: [5, 10, 15, 20]

2. Step 2: Pop n-1=2 times and then pop once more for value

   Pop 1: 20, Pop 2: 15, final pop returns 10 which is the 3rd from end

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   3rd from end in [5,10,15,20] is 10 [OK]

Hint: Stack top is last node; pop n times to get nth from end [OK]

Common Mistakes:

• Off-by-one popping
• Returning node instead of value
• Confusing index from front vs end

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

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

4. What is the time complexity of the optimal one-pass splitting algorithm for splitting a linked list of length n into k parts, and why?

medium

A. O(n + k) because we first count nodes in O(n) and then split in O(k) steps.

B. O(n * k) because for each of the k parts, we traverse nodes up to part size.

C. O(n) because we only traverse the list once without extra passes.

D. O(k) because we only create k parts and do constant work per part.

Solution

1. Step 1: Analyze counting nodes

   Counting total nodes requires traversing the entire list once -> O(n).

2. Step 2: Analyze splitting parts

   Splitting involves iterating over k parts and moving pointers, total steps sum to n nodes plus k iterations -> O(n + k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counting + splitting both contribute; total is O(n + k) [OK]

Hint: Counting nodes plus splitting parts sums to O(n + k) [OK]

Common Mistakes:

• Assuming O(n*k) due to nested loops
• Ignoring counting step
• Confusing k with n

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