Circular Array Loop

📋

Problem

Imagine a circular conveyor belt with sections moving forward or backward. You want to detect if there's a loop where a package could keep moving endlessly in one direction.

Given a circular array nums of integers, where each element represents the number of steps to move forward (positive) or backward (negative), determine if there is a cycle in the array. The cycle must be strictly longer than 1 element and all steps in the cycle must move in the same direction (all positive or all negative). Return true if such a cycle exists, otherwise false.

1 ≤ nums.length ≤ 10^5-10^5 ≤ nums[i] ≤ 10^5nums[i] ≠ 0

Edge cases: Single element array [1] → false (cycle length must be > 1)All elements same positive number [1,1,1,1] → true (full cycle)Array with zero steps [0,1,2] → invalid input as per constraints

</>

IDE

def circularArrayLoop(nums: list[int]) -> bool:public boolean circularArrayLoop(int[] nums)bool circularArrayLoop(vector<int>& nums)function circularArrayLoop(nums)

def circularArrayLoop(nums):
    # Write your solution here
    pass

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool circularArrayLoop(vector<int>& nums) {
    // Write your solution here
    return false;
}

function circularArrayLoop(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for single element arrayFailed to check cycle length > 1, returning true for trivial cycles.✅ Add condition to verify cycle length is strictly greater than 1 before returning true.

Wrong: true for mixed direction cyclesDid not enforce direction consistency within detected cycles.✅ Check that all elements in the cycle have the same sign before confirming cycle.

Wrong: false for valid cycles with negative stepsFailed to detect cycles moving backward or handle negative indices correctly.✅ Use modulo arithmetic carefully and ensure direction consistency check includes negative direction.

Wrong: true for non-cycles due to greedy approachAssumed any forward step forms a cycle without proper cycle detection.✅ Implement fast and slow pointer cycle detection instead of greedy assumptions.

Wrong: TLE on large inputsUsing brute force O(n^2) simulation from each index.✅ Optimize to O(n) fast and slow pointer approach with early exits.

✓

Test Cases

Focus on handling small inputs and direction consistency for cycles.

Watch out for common algorithmic pitfalls like greedy assumptions and cycle length checks.

Optimize your solution to O(n) time using fast and slow pointers to handle large inputs.

t1_01basic

Input{"nums":[2,-1,1,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

There is a cycle: index 0 -> 2 -> 3 -> 0, all moving forward.

💡 Consider using fast and slow pointers to detect cycles in the array.

💡 Check that all elements in the cycle move in the same direction (all positive or all negative).

💡 Return true if a cycle longer than 1 element is found with consistent direction.

Why it failed: Returned false or no cycle detected; likely missed checking direction consistency or cycle length > 1. Fix by verifying direction and cycle length before returning true.

✓ Correctly detected a valid cycle with consistent direction and length > 1.

t1_02basic

Input{"nums":[-2,1,-1,-2,-2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Cycle exists: index 0 -> 3 -> 0 moving backward consistently.

💡 Try detecting cycles starting from each index with fast and slow pointers.

💡 Ensure the cycle moves in one consistent direction (all negative here).

💡 Confirm cycle length is greater than 1 before returning true.

Why it failed: Returned false or missed cycle; likely failed to handle negative direction cycles or cycle length check. Fix by enforcing direction consistency and length > 1.

✓ Correctly identified a backward cycle with consistent direction and length > 1.

t2_01edge

Input{"nums":[1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element cannot form a cycle longer than 1.

💡 Check if the array length is less than 2, cycles longer than 1 are impossible.

💡 Remember cycle length must be strictly greater than 1.

💡 Return false immediately if array length is 1.

Why it failed: Returned true incorrectly; failed to enforce cycle length > 1. Fix by adding cycle length check before returning true.

✓ Correctly returned false for single element array with no valid cycle.

t2_02edge

Input{"nums":[1,1,1,1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

All elements same positive number form a full cycle moving forward.

💡 Check if all elements move in the same direction and form a cycle.

💡 Use fast and slow pointers to detect the full cycle.

💡 Confirm cycle length > 1 and consistent direction before returning true.

Why it failed: Returned false; likely failed to detect full cycle with identical positive steps. Fix by ensuring cycle detection covers all indices and direction consistency.

✓ Correctly detected full cycle with identical positive steps.

t2_03edge

Input{"nums":[1,-1,1,-1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

No cycle because direction consistency fails (mixed positive and negative).

💡 Check direction consistency for each potential cycle.

💡 If directions differ within a cycle, it is invalid.

💡 Return false if no consistent direction cycle longer than 1 is found.

Why it failed: Returned true incorrectly; failed to enforce direction consistency. Fix by verifying all steps in cycle have same sign.

✓ Correctly returned false due to mixed directions preventing valid cycle.

t3_01corner

Input{"nums":[3,1,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy approach fails here; no valid cycle exists despite multiple jumps.

💡 Beware of greedy approaches that assume any forward step forms a cycle.

💡 Use fast and slow pointers to confirm actual cycles.

💡 Check cycle length and direction consistency strictly.

Why it failed: Returned true incorrectly; greedy approach mistake assuming any forward steps form cycle. Fix by using fast-slow pointer cycle detection with direction checks.

✓ Correctly returned false by detecting no valid cycle despite multiple steps.

t3_02corner

Input{"nums":[1,2,3,4,5]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Cycle exists moving forward through all indices; tests 0/1 vs unbounded confusion.

💡 Remember this is a 0/1 cycle detection problem, not unbounded jumps.

💡 Use fast and slow pointers to detect cycles correctly.

💡 Ensure cycle length > 1 and consistent direction before returning true.

Why it failed: Returned false; confused 0/1 cycle detection with unbounded jumps. Fix by implementing proper cycle detection with fast and slow pointers.

✓ Correctly detected cycle with consistent forward direction and length > 1.

t3_03corner

Input{"nums":[1,2,-1,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Cycle exists ignoring the negative step that breaks direction consistency if included.

💡 Check direction consistency carefully; cycles must not include elements with opposite sign.

💡 Fast and slow pointers must skip invalid cycles with mixed directions.

💡 Return true only for cycles with consistent direction and length > 1.

Why it failed: Returned false; failed to exclude mixed direction elements from cycle detection. Fix by enforcing direction consistency strictly during traversal.

✓ Correctly detected cycle ignoring elements that break direction consistency.

t4_01performance

Input{"nums":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) fast-slow pointer cycle detection must complete within 2 seconds.

💡 Use fast and slow pointers to achieve O(n) time complexity.

💡 Avoid nested loops or brute force simulation from each index.

💡 Early exit when cycle detected or all elements processed.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing O(n) fast-slow pointer cycle detection.

✓ Algorithm runs in O(n) time confirming efficient cycle detection.

Practice

1. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

2. Identify the bug in the following code snippet for finding the duplicate number using Floyd's cycle detection:

medium

A. The initialization of slow and fast pointers is incorrect

B. The second while loop incorrectly updates fast pointer

C. The first while loop condition causes an infinite loop

D. The return statement should return fast instead of slow

Solution

1. Step 1: Examine the first while loop condition

   The loop condition is while slow != fast, but slow and fast are initialized to the same value, so the loop never runs, causing no intersection point found.

2. Step 2: Understand consequences

   Without the loop running, slow and fast pointers do not move, so the algorithm fails to detect the cycle and returns incorrect result or loops infinitely if code is modified.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop condition must allow first iteration; using while True with break is correct [OK]

Hint: First loop must run at least once to find intersection [OK]

Common Mistakes:

• Using while slow != fast before pointers move
• Incorrect pointer updates inside loops
• Returning wrong pointer at the end

3. Consider the following buggy code snippet for splitting a linked list into k parts. Which line contains the subtle bug that can cause parts to remain connected, leading to incorrect output or infinite loops?

medium

A. Line where current.next is set to null (missing in this code)

B. Line where parts[i] is assigned

C. Line where remainder is decremented

D. Line where total_nodes is counted

Solution

1. Step 1: Identify missing link break

   The code comments out the lines that break the link after each part, so parts remain connected.

2. Step 2: Understand impact

   Without setting current.next = null, parts share nodes, causing incorrect output or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Breaking links is essential to separate parts [OK]

Hint: Always break links to separate parts [OK]

Common Mistakes:

• Forgetting to break links
• Misplacing remainder decrement
• Incorrectly assigning parts[i]

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