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. Consider the following Python code implementing the optimal Happy Number check using a known cycle set. What is the output when the input is 7?

def isHappy(n: int) -> bool:
    cycle_set = {4, 16, 37, 58, 89, 145, 42, 20}

    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    while n != 1 and n not in cycle_set:
        n = get_next(n)
    return n == 1

print(isHappy(7))

easy

A. Runtime error due to infinite loop

B. null (function returns no value)

C. true

D. false

Solution

1. Step 1: Trace the sequence starting from 7

   7 -> 49 (4²+9²=16+81=97) -> 97 -> 130 -> 10 -> 1 Detailed steps: 7 -> 49 (4²+9²=16+81=97) 97 -> 130 (9²+7²=81+49=130) 130 -> 10 (1²+3²+0²=1+9+0=10) 10 -> 1 (1²+0²=1+0=1) So it reaches 1.

2. Step 2: Check if the code returns true for n=7

   The loop terminates when n == 1, so the function returns true.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sequence reaches 1 -> returns true [OK]

Hint: Trace sum-of-squares sequence carefully [OK]

Common Mistakes:

• Miscompute sum of squares leading to wrong cycle detection

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

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

4. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle and counting its length in a linked list of n nodes?

medium

A. O(n²) because the inner loop counts cycle length after detection

B. O(n) because fast and slow pointers traverse nodes at most twice

C. O(n log n) due to repeated pointer jumps

D. O(n) but with O(n) auxiliary space for visited nodes

Solution

1. Step 1: Analyze fast and slow pointer traversal

   Fast pointer moves twice as fast as slow, so they meet within O(n) steps.

2. Step 2: Count cycle length with a single traversal

   After detection, counting cycle length requires traversing the cycle once, which is O(k) ≤ O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is linear in number of nodes [OK]

Hint: Fast-slow pointers meet in O(n), counting cycle is O(k) ≤ O(n) [OK]

Common Mistakes:

• Assuming counting cycle length is O(n²)
• Confusing space complexity with time
• Thinking recursion or extra data structures are used

5. What is the space complexity of the recursive backtracking solution to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(log n) -- recursion divides the list in half each call

C. O(n) -- due to auxiliary arrays storing node references

D. O(n) -- due to recursion stack depth proportional to list length

Solution

1. Step 1: Identify recursion depth

   The recursion visits each node once, so the call stack depth is n.

2. Step 2: Understand space usage

   No extra arrays or data structures are used, but the recursion stack itself uses O(n) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack proportional to list length n [OK]

Hint: Recursion stack uses O(n) space even if no extra arrays used [OK]

Common Mistakes:

• Assuming recursion uses constant space
• Confusing recursion with divide-and-conquer halving
• Thinking auxiliary arrays are used