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

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 array can contain multiple duplicates and some numbers appear more than twice. Which modification to Floyd's cycle detection algorithm correctly finds any duplicate number?

hard

A. No modification needed; Floyd's algorithm works regardless of duplicate count

B. Use a hash set to track visited numbers instead of cycle detection

C. Run Floyd's algorithm multiple times, removing found duplicates each time

D. Floyd's algorithm still works because the cycle corresponds to any duplicate, even if repeated

Solution

1. Step 1: Understand Floyd's algorithm behavior with multiple duplicates

   The cycle in the array corresponds to the repeated number's indices. Even if duplicates appear multiple times, the cycle exists and Floyd's algorithm detects its entrance.

2. Step 2: Confirm no need for multiple runs or extra data structures

   Floyd's algorithm finds one duplicate per run. It does not require modification to detect duplicates repeated more than twice.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection finds the cycle entrance regardless of duplicate frequency [OK]

Hint: Cycle entrance corresponds to duplicate regardless of count [OK]

Common Mistakes:

• Assuming Floyd's algorithm only works if duplicate appears twice
• Thinking multiple runs or extra space are needed
• Confusing cycle detection with hash-based methods

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