Find Cycle in Array (Jump Game)

📋

Problem

Imagine a game where you jump through an array using the values as steps, and you want to know if you can get stuck in an infinite loop.

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

1 ≤ n ≤ 10^5-10^5 ≤ nums[i] ≤ 10^5nums[i] ≠ 0 for all i

Edge cases: Array with all positive numbers forming a cycle → trueArray with all negative numbers forming a cycle → trueArray with single element → false (cycle length must be > 1)

</>

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 arrayMissing cycle length > 1 check, treating self-loop as valid cycle.✅ Add condition to verify next_index != current_index before returning true.

Wrong: false for all positive identical elements forming cycleBreaking early or not detecting full cycle in uniform arrays.✅ Ensure cycle detection runs through entire array and checks direction consistency.

Wrong: true for mixed direction jumps cycleNot enforcing direction consistency in cycle detection.✅ Add check that all jumps in cycle have the same sign before returning true.

Wrong: true for greedy jump assumption without cycleAssuming any forward jump forms a cycle without verifying cycle length or direction.✅ Use fast and slow pointers to detect actual cycles and verify conditions.

Wrong: TLE on large inputUsing brute force simulation with O(n^2) complexity.✅ Implement Floyd's cycle detection algorithm with O(n) time complexity.

✓

Test Cases

Focus on handling small and boundary inputs correctly, especially single elements and uniform arrays.

Think about common pitfalls like greedy traps and direction inconsistencies in cycle detection.

Optimize your solution to linear time using fast and slow pointers to handle large inputs efficiently.

t1_01basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Starting at index 0, jump 2 steps to index 2, then jump 1 step to index 3, then jump 2 steps to index 0 again, forming a cycle.

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

💡 Check if the cycle is all in one direction and longer than 1 element.

💡 Ensure you skip cycles of length 1 and verify direction consistency.

Why it failed: Failed to detect the cycle starting at index 0. Possibly missed checking cycle length > 1 or direction consistency. Fix by verifying next index != current and all jumps have same sign.

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

t1_02basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

No valid cycle exists because jumps break direction consistency or cycle length is 1. Starting at index 0 or 3 does not form a valid cycle with consistent direction and length > 1.

💡 Try detecting cycles starting from different indices with consistent jump directions.

💡 Use fast and slow pointers to find cycles and ensure all jumps have the same sign.

💡 Remember to ignore cycles of length 1 and confirm direction consistency before returning true.

Why it failed: Incorrectly returned true or missed that no valid cycle exists. Fix by ensuring direction consistency check includes negative jumps and cycle length > 1.

✓ Correctly identified no valid cycle exists.

t2_01edge

Input{"nums":[0]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array cannot form a cycle longer than 1 element.

💡 Check the minimum cycle length required is greater than 1.

💡 A single element pointing to itself forms a cycle of length 1, which is invalid.

💡 Return false if array length is 1 or if cycle length is 1.

Why it failed: Returned true for single element self-loop. Fix by adding cycle length > 1 check before returning true. This is the single element test.

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

t2_02edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

All positive jumps form a cycle covering the entire array.

💡 Test arrays where all elements have the same positive value forming a cycle.

💡 Ensure your cycle detection works for cycles that include all elements.

💡 Verify direction consistency and cycle length > 1 for full array cycles.

Why it failed: Failed to detect cycle in all-positive array. Fix by not breaking early and checking full cycle with consistent positive direction. This is the all identical positive elements test.

✓ Correctly detected cycle in all positive identical elements array.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

All negative jumps form a cycle covering the entire array.

💡 Test arrays where all elements have the same negative value forming a cycle.

💡 Ensure your cycle detection works for cycles that include all elements with negative direction.

💡 Verify direction consistency and cycle length > 1 for full array cycles.

Why it failed: Failed to detect cycle in all-negative array. Fix by ensuring direction consistency check includes negative jumps and cycle length > 1. This is the all identical negative elements test.

✓ Correctly detected cycle in all negative identical elements array.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

A cycle exists starting at index 0: 0->1->3->2->0 with all positive jumps and length > 1.

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

💡 Check that cycle length is greater than 1 and direction is consistent.

💡 Fix by using fast and slow pointers to detect cycles properly, not greedy jumps.

Why it failed: Returned false incorrectly due to greedy assumption that no cycle exists. Fix by implementing fast-slow pointer cycle detection with direction and length checks. This is the greedy trap test.

✓ Correctly detected the cycle by avoiding greedy false negatives.

t3_02corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Cycle exists only in positive direction elements ignoring negative jump at last index.

💡 Distinguish between 0/1 knapsack style confusion and this problem's direction consistency.

💡 Ensure you do not mix directions when detecting cycles.

💡 Fix by checking all jumps in cycle have same sign and cycle length > 1.

Why it failed: Incorrectly returned false due to mixing directions or treating negative jumps as cycle parts. Fix by enforcing direction consistency in cycle detection. This is the 0/1 vs unbounded confusion test.

✓ Correctly detected cycle respecting direction consistency.

t3_03corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

A valid cycle exists among the first three positive jumps; negative jumps do not form a cycle.

💡 Check that cycles must be all positive or all negative jumps.

💡 Detect and reject cycles that include mixed directions.

💡 Fix by verifying direction consistency before confirming cycle.

Why it failed: Returned false incorrectly for mixed direction jumps cycle. Fix by adding direction consistency check for all elements in cycle. This is the mixed direction cycle test.

✓ Correctly detected cycle among consistent direction jumps.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 all positive jumps forming a cycle. Algorithm must run in O(n) time to avoid TLE.

💡 Use fast and slow pointer technique for O(n) cycle detection.

💡 Avoid brute force simulation with O(n^2) complexity.

💡 Mark visited elements to skip redundant checks and achieve linear time.

Why it failed: TLE due to brute force O(n^2) approach. Fix by implementing Floyd's cycle detection with O(n) complexity. This is the performance test.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given a circular array where each element represents a jump length and direction (positive for forward, negative for backward). The task is to determine if there exists a cycle in the array such that the cycle is longer than one element and all jumps are in the same direction. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to jump as far as possible from each index until a cycle is detected or no progress is made.

B. Dynamic programming to store reachable indices and detect cycles by memoization.

C. Brute force simulation from each index checking all possible cycles exhaustively.

D. Fast and slow pointer cycle detection that checks direction consistency and avoids single-element loops.

Solution

1. Step 1: Understand problem constraints

   The problem requires detecting cycles in a circular array with direction consistency and cycle length > 1.

2. Step 2: Identify suitable algorithm

   Fast and slow pointer cycle detection efficiently finds cycles in O(n) time while checking direction and cycle length constraints.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast and slow pointers detect cycles without exhaustive search [OK]

Hint: Cycle detection with direction check -> fast-slow pointers [OK]

Common Mistakes:

• Assuming greedy jumps always find cycles
• Using DP which is inefficient here
• Brute force is correct but not optimal

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. Suppose the problem is modified so that after deleting N nodes, the deleted nodes can be reinserted later in the list (i.e., nodes can be reused). Which of the following changes to the algorithm is necessary to correctly handle this variant?

hard

A. Use a recursive approach to backtrack and reinsert deleted nodes at correct positions.

B. Maintain a separate data structure to store deleted nodes and reinsert them after traversal.

C. Modify the iterative approach to skip M nodes, delete N nodes, and immediately reattach deleted nodes after the next M nodes.

D. No change needed; the original iterative approach already supports node reuse.

Solution

1. Step 1: Understand node reuse requirement

   Deleted nodes must be preserved and reinserted later, so they cannot be simply discarded by pointer reassignment.

2. Step 2: Evaluate algorithm changes

   The original approach loses references to deleted nodes. To reuse, store deleted nodes externally and reinsert after traversal or at correct positions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maintaining deleted nodes separately enables controlled reinsertion [OK]

Hint: Reusing nodes requires storing them, not discarding pointers [OK]

Common Mistakes:

• Assuming original approach supports reuse
• Trying to reattach nodes immediately without storage
• Using recursion unnecessarily

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

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily