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 Python code for checking if a number is happy. The code attempts to detect cycles using recursion but lacks proper cycle detection.

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    def helper(num):
        if num == 1:
            return true
        return helper(get_next(num))

    return helper(n)

medium

A. Missing base case for cycle detection causing infinite recursion

B. Incorrect sum of squares calculation in get_next function

C. Returning helper(get_next(num)) without checking if num is 1

D. Not initializing total_sum to zero before summing digits

Solution

1. Step 1: Analyze recursion base cases

   The code only stops recursion if num == 1. It does not detect cycles, so for unhappy numbers it recurses infinitely.

2. Step 2: Identify missing cycle detection

   Without tracking visited numbers or using fast-slow pointers, the recursion never terminates for cycles, causing stack overflow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite recursion due to missing cycle detection base case [OK]

Hint: Check for cycle detection in recursion to avoid infinite loops [OK]

Common Mistakes:

• Assuming recursion stops at cycles without explicit detection

3. What is the time and space complexity of the optimal single-pass two-pointer approach to find the middle node of a singly linked list with n nodes?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(log n), Space: O(1)

Solution

1. Step 1: Identify time complexity

   Fast pointer moves two steps per iteration, slow moves one; total iterations proportional to n -> O(n) time.

2. Step 2: Identify space complexity

   Only two pointers used, no extra data structures -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for two-pointer traversal [OK]

Hint: Two pointers traverse list once, no extra storage [OK]

Common Mistakes:

• Confusing space with O(n) due to recursion
• Assuming nested loops cause O(n^2)
• Thinking fast pointer halves complexity to O(log n)

4. What is the space complexity of the optimal palindrome linked list check that reverses the second half in-place?

medium

A. O(n) due to storing node values in an array

B. O(1) because reversal is done in-place without extra data structures

C. O(log n) due to recursion stack in reversal

D. O(n) due to recursion stack in reversal

Solution

1. Step 1: Identify auxiliary space usage

   The algorithm reverses the second half in-place using pointers, no extra arrays or stacks.

2. Step 2: Check for recursion stack

   The reversal is iterative, so no recursion stack space is used.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   In-place iterative reversal uses constant extra space [OK]

Hint: Iterative reversal uses O(1) space, recursion would add stack space [OK]

Common Mistakes:

• Confusing iterative reversal with recursive reversal
• Assuming array storage is needed for palindrome check
• Forgetting recursion stack space in complexity

5. If the linked list nodes cannot be modified (no extra fields allowed) and you want to detect a cycle in O(1) space, which approach correctly adapts Floyd's cycle detection algorithm to also find the entry point of the cycle?

hard

A. Use a hash set to store nodes and find the first repeated node as the cycle start.

B. Modify node values temporarily to mark visited nodes and revert after detection.

C. After detecting the cycle, reset slow to head and move both pointers one step at a time until they meet; the meeting point is the cycle start.

D. Run the fast pointer twice as fast until it reaches the end, then backtrack to find the cycle start.

Solution

1. Step 1: Detect cycle using fast and slow pointers

   When fast and slow meet, a cycle exists but the meeting point is not necessarily the cycle start.

2. Step 2: Find cycle entry point

   Reset slow to head, then move slow and fast one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard Floyd's algorithm extension for cycle entry detection [OK]

Hint: Reset slow to head after detection to find cycle start [OK]

Common Mistakes:

• Using extra memory when O(1) space required
• Modifying node values disallowed
• Incorrect pointer movement after detection