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

2. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here

3. Suppose the linked list can have multiple cycles due to node reuse (e.g., a node's next pointer can point to any previously visited node, creating multiple cycle entries). Which modification to Floyd's algorithm correctly detects the first cycle start node encountered from the head?

hard

A. Run Floyd's algorithm repeatedly after removing detected cycles until no cycle remains.

B. Use two pointers but move fast pointer three steps at a time to detect multiple cycles faster.

C. Modify Floyd's algorithm to reset the fast pointer to head after detection and continue until slow and fast meet again.

D. Use a hash set to track visited nodes and return the first repeated node encountered during traversal.

Solution

1. Step 1: Understand multiple cycles scenario

   Floyd's algorithm assumes a single cycle; multiple cycles break its assumptions and can cause incorrect detection.

2. Step 2: Use hash set to detect first repeated node

   Tracking visited nodes with a hash set detects the first node that appears twice, correctly identifying the earliest cycle entry.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach works correctly with multiple cycles but uses extra space [OK]

Hint: Floyd's algorithm fails with multiple cycles; hash set detects first repeated node [OK]

Common Mistakes:

• Trying to adapt Floyd's algorithm without extra space
• Assuming multiple cycles can't exist
• Increasing fast pointer speed doesn't help

4. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better

5. Suppose the problem is modified so that the linked list nodes can be reused multiple times in different parts (i.e., parts can share nodes). Which of the following changes to the original splitting algorithm correctly adapts to this new requirement?

hard

A. Split the list into k parts by creating new linked lists from scratch for each part, ignoring original links.

B. Keep the original algorithm but duplicate nodes when assigning to parts to avoid shared references.

C. Remove the step that breaks the link (current.next = null) after each part, allowing parts to share nodes.

D. Use a greedy approach assigning nodes to parts without precomputing sizes, since reuse allows overlap.

Solution

1. Step 1: Understand reuse requirement

   Nodes can appear in multiple parts, so links should not be broken to preserve shared nodes.

2. Step 2: Adapt algorithm

   Removing the link-breaking step allows parts to share nodes as required.

3. Step 3: Evaluate other options

   Duplicating nodes or creating new lists is unnecessary and inefficient; greedy without sizes breaks constraints.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Not breaking links enables node reuse [OK]

Hint: Remove link breaks to allow node reuse [OK]

Common Mistakes:

• Duplicating nodes unnecessarily
• Breaking links despite reuse
• Ignoring size constraints