Circular Array Loop

🎯

Circular Array Loop

mediumTWO_POINTERAmazonGoogle

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.

💡 This problem is about detecting cycles in a circular array where each element tells you how far to jump next. Beginners often struggle because the cycle detection must consider direction consistency and handle wrapping around the array, which is unlike typical linked list cycles.

📋

Problem Statement

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

💡

Example

Input"[2, -1, 1, 2, 2]"

Outputtrue

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

Input"[-1, 2]"

Outputfalse

No cycle exists because the directions are inconsistent.

• 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
• Cycle with mixed directions [1,-1,1,-1] → false (direction consistency fails)

⚠️

Common Mistakes

Not handling direction consistency

Incorrectly detects cycles that change direction

✅ Always check if current step direction matches initial direction

Counting single-element loops as valid cycles

Returns true for loops of length 1, which is invalid

✅ Check if next index equals current index and ignore such loops

Not marking visited elements to avoid repeated work

Algorithm runs slower and may time out

✅ Mark visited indices (e.g., set to 0) after processing

Incorrect modulo operation causing negative indices

Array index out of bounds or wrong next index

✅ Use (index + nums[index]) % n and add n if result is negative

🧠

Brute Force (Simulation from Each Index)

💡 This approach tries to simulate the movement starting from each index to find a cycle. It is straightforward and helps understand the problem deeply, but it is inefficient for large inputs.

Intuition

Try starting from every index and follow the jumps until you either find a cycle or break the rules (direction change or single-element loop).

Algorithm

1. For each index in the array, start simulating jumps.
2. Keep track of visited indices in this simulation to detect cycles.
3. If a cycle is found with length > 1 and consistent direction, return true.
4. If no cycle found after checking all indices, return false.

💡 The nested loops and direction checks make this approach hard to optimize but easy to understand the problem mechanics.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    for i in range(n):
        direction = nums[i] > 0
        visited = set()
        current = i
        while True:
            if nums[current] > 0 != direction:
                break
            next_index = (current + nums[current]) % n
            if next_index == current:
                break
            if next_index in visited:
                return True
            visited.add(current)
            current = next_index
    return False

# Driver code
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

for i in range(n):Try starting simulation from every index to find any cycle.

direction = nums[i] > 0Determine the movement direction to ensure consistency.

visited = set()Track visited indices in current simulation to detect cycles.

if nums[current] > 0 != direction:Break if direction changes, violating problem constraints.

next_index = (current + nums[current]) % nCalculate next index with wrap-around using modulo.

if next_index == current:Break if cycle length is 1, which is invalid.

if next_index in visited:Cycle detected if we revisit an index in the current path.

visited.add(current)Mark current index as visited before moving on.

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean direction = nums[i] > 0;
            Set<Integer> visited = new HashSet<>();
            int current = i;
            while (true) {
                if ((nums[current] > 0) != direction) break;
                int next = ((current + nums[current]) % n + n) % n;
                if (next == current) break;
                if (visited.contains(next)) return true;
                visited.add(current);
                current = next;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

for (int i = 0; i < n; i++) {Start simulation from each index to find cycles.

boolean direction = nums[i] > 0;Determine movement direction for consistency check.

Set<Integer> visited = new HashSet<>();Track visited indices in current simulation.

if ((nums[current] > 0) != direction) break;Stop if direction changes, invalid cycle.

int next = ((current + nums[current]) % n + n) % n;Calculate next index with wrap-around, handle negatives.

if (next == current) break;Ignore single-element loops.

if (visited.contains(next)) return true;Cycle detected if revisiting an index.

visited.add(current);Mark current index visited before moving.

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            bool direction = nums[i] > 0;
            unordered_set<int> visited;
            int current = i;
            while (true) {
                if ((nums[current] > 0) != direction) break;
                int next = ((current + nums[current]) % n + n) % n;
                if (next == current) break;
                if (visited.count(next)) return true;
                visited.insert(current);
                current = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Try starting simulation from each index to find cycles.

bool direction = nums[i] > 0;Determine movement direction for consistency.

unordered_set<int> visited;Track visited indices in current simulation.

if ((nums[current] > 0) != direction) break;Stop if direction changes, invalid cycle.

int next = ((current + nums[current]) % n + n) % n;Calculate next index with wrap-around, handle negatives.

if (next == current) break;Ignore single-element loops.

if (visited.count(next)) return true;Cycle detected if revisiting an index.

visited.insert(current);Mark current index visited before moving.

var circularArrayLoop = function(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const direction = nums[i] > 0;
        const visited = new Set();
        let current = i;
        while (true) {
            if ((nums[current] > 0) !== direction) break;
            let next = (current + nums[current]) % n;
            if (next < 0) next += n;
            if (next === current) break;
            if (visited.has(next)) return true;
            visited.add(current);
            current = next;
        }
    }
    return false;
};

// Test cases
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

for (let i = 0; i < n; i++) {Start simulation from each index to find cycles.

const direction = nums[i] > 0;Determine movement direction for consistency.

const visited = new Set();Track visited indices in current simulation.

if ((nums[current] > 0) !== direction) break;Stop if direction changes, invalid cycle.

let next = (current + nums[current]) % n;Calculate next index with wrap-around.

if (next < 0) next += n;Adjust negative modulo results to positive indices.

if (next === current) break;Ignore single-element loops.

if (visited.has(next)) return true;Cycle detected if revisiting an index.

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each of the n indices, we may visit up to n elements in the worst case, leading to O(n^2). The visited set uses O(n) space per simulation.

💡 For n=1000, this means up to 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and verify correctness on small cases.

🧠

Fast & Slow Pointer Cycle Detection

💡 This approach uses two pointers moving at different speeds to detect cycles efficiently, inspired by Floyd's cycle detection in linked lists. It avoids extra space and reduces time complexity.

Intuition

Use a slow pointer moving one step and a fast pointer moving two steps. If they meet, a cycle exists. Check direction consistency and cycle length > 1.

Algorithm

1. Iterate over each index as a potential cycle start.
2. If the element is not visited, use fast and slow pointers to detect a cycle.
3. Move pointers while direction is consistent and cycle length > 1.
4. If pointers meet, return true; else mark all visited indices in this path to avoid reprocessing.

💡 The challenge is to handle direction consistency and avoid infinite loops by marking visited elements.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    def next_index(i):
        return (i + nums[i]) % n

    for i in range(n):
        if nums[i] == 0:
            continue
        direction = nums[i] > 0
        slow, fast = i, i
        while True:
            slow = next_index(slow)
            fast = next_index(next_index(fast))
            if (nums[slow] > 0) != direction or (nums[fast] > 0) != direction:
                break
            if slow == fast:
                if slow == next_index(slow):
                    break
                return True
        slow = i
        val = nums[i]
        while (nums[slow] > 0) == direction:
            next_i = next_index(slow)
            nums[slow] = 0
            slow = next_i
    return False

# Driver code
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

def next_index(i):Helper to compute next index with wrap-around.

if nums[i] == 0:Skip already visited or processed elements.

direction = nums[i] > 0Determine movement direction for consistency.

slow, fast = i, iInitialize two pointers at the start index.

slow = next_index(slow)Move slow pointer one step.

fast = next_index(next_index(fast))Move fast pointer two steps.

if (nums[slow] > 0) != direction or (nums[fast] > 0) != direction:Break if direction changes.

if slow == fast:Cycle detected if pointers meet.

if slow == next_index(slow):Ignore single-element loops.

nums[slow] = 0Mark visited elements to avoid reprocessing.

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            boolean direction = nums[i] > 0;
            int slow = i, fast = i;
            while (true) {
                slow = nextIndex(nums, n, slow);
                fast = nextIndex(nums, n, nextIndex(nums, n, fast));
                if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;
                if (slow == fast) {
                    if (slow == nextIndex(nums, n, slow)) break;
                    return true;
                }
            }
            slow = i;
            int val = nums[i];
            while ((nums[slow] > 0) == direction) {
                int next = nextIndex(nums, n, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }

    private int nextIndex(int[] nums, int n, int i) {
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

if (nums[i] == 0) continue;Skip elements already processed to avoid redundant work.

boolean direction = nums[i] > 0;Determine movement direction for consistency.

int slow = i, fast = i;Initialize two pointers at the start index.

slow = nextIndex(nums, n, slow);Move slow pointer one step.

fast = nextIndex(nums, n, nextIndex(nums, n, fast));Move fast pointer two steps.

if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;Break if direction changes.

if (slow == fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited elements to avoid reprocessing.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int nextIndex(vector<int>& nums, int n, int i) {
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            bool direction = nums[i] > 0;
            int slow = i, fast = i;
            while (true) {
                slow = nextIndex(nums, n, slow);
                fast = nextIndex(nums, n, nextIndex(nums, n, fast));
                if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;
                if (slow == fast) {
                    if (slow == nextIndex(nums, n, slow)) break;
                    return true;
                }
            }
            slow = i;
            while ((nums[slow] > 0) == direction) {
                int next = nextIndex(nums, n, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

if (nums[i] == 0) continue;Skip elements already processed to avoid redundant work.

bool direction = nums[i] > 0;Determine movement direction for consistency.

int slow = i, fast = i;Initialize two pointers at the start index.

slow = nextIndex(nums, n, slow);Move slow pointer one step.

fast = nextIndex(nums, n, nextIndex(nums, n, fast));Move fast pointer two steps.

if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;Break if direction changes.

if (slow == fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited elements to avoid reprocessing.

var circularArrayLoop = function(nums) {
    const n = nums.length;
    const nextIndex = (i) => {
        let next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    };

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        const direction = nums[i] > 0;
        let slow = i, fast = i;
        while (true) {
            slow = nextIndex(slow);
            fast = nextIndex(nextIndex(fast));
            if ((nums[slow] > 0) !== direction || (nums[fast] > 0) !== direction) break;
            if (slow === fast) {
                if (slow === nextIndex(slow)) break;
                return true;
            }
        }
        slow = i;
        while ((nums[slow] > 0) === direction) {
            let next = nextIndex(slow);
            nums[slow] = 0;
            slow = next;
        }
    }
    return false;
};

// Test cases
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

if (nums[i] === 0) continue;Skip elements already processed to avoid redundant work.

const direction = nums[i] > 0;Determine movement direction for consistency.

let slow = i, fast = i;Initialize two pointers at the start index.

slow = nextIndex(slow);Move slow pointer one step.

fast = nextIndex(nextIndex(fast));Move fast pointer two steps.

if ((nums[slow] > 0) !== direction || (nums[fast] > 0) !== direction) break;Break if direction changes.

if (slow === fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited elements to avoid reprocessing.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most once due to marking visited elements as 0, so total time is linear. Space is constant as no extra data structures are used.

💡 For n=100000, this approach can handle all elements efficiently within time limits.

Interview Verdict: Accepted

This is the optimal approach commonly expected in interviews for cycle detection in arrays.

🧠

Optimized Fast & Slow Pointer with Early Exit

💡 This approach improves the previous by adding early exit conditions and minor optimizations to reduce unnecessary checks, making it cleaner and slightly faster in practice.

Intuition

Add checks to skip indices that cannot form cycles early and avoid redundant computations by marking visited elements promptly.

Algorithm

1. Iterate over each index, skip if already visited (marked 0).
2. Use fast and slow pointers to detect cycle with direction consistency.
3. If cycle found, return true immediately.
4. If no cycle, mark all nodes in current traversal as visited (0) to avoid reprocessing.

💡 Marking visited nodes early prevents repeated work and speeds up the algorithm.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    def next_index(i):
        return (i + nums[i]) % n

    for i in range(n):
        if nums[i] == 0:
            continue
        direction = nums[i] > 0
        slow, fast = i, i
        while True:
            slow = next_index(slow)
            fast = next_index(next_index(fast))
            if (nums[slow] > 0) != direction or (nums[fast] > 0) != direction:
                break
            if slow == fast:
                if slow == next_index(slow):
                    break
                return True
        slow = i
        while (nums[slow] > 0) == direction:
            next_i = next_index(slow)
            nums[slow] = 0
            slow = next_i
    return False

# Driver code
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

if nums[i] == 0:Skip indices already processed to avoid redundant checks.

direction = nums[i] > 0Determine movement direction for cycle consistency.

slow, fast = i, iInitialize pointers for cycle detection.

slow = next_index(slow)Move slow pointer one step.

fast = next_index(next_index(fast))Move fast pointer two steps.

if (nums[slow] > 0) != direction or (nums[fast] > 0) != direction:Break if direction changes.

if slow == fast:Cycle detected if pointers meet.

nums[slow] = 0Mark visited nodes to prevent reprocessing.

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            boolean direction = nums[i] > 0;
            int slow = i, fast = i;
            while (true) {
                slow = nextIndex(nums, n, slow);
                fast = nextIndex(nums, n, nextIndex(nums, n, fast));
                if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;
                if (slow == fast) {
                    if (slow == nextIndex(nums, n, slow)) break;
                    return true;
                }
            }
            slow = i;
            while ((nums[slow] > 0) == direction) {
                int next = nextIndex(nums, n, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }

    private int nextIndex(int[] nums, int n, int i) {
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

if (nums[i] == 0) continue;Skip already processed indices to save time.

boolean direction = nums[i] > 0;Determine movement direction for cycle detection.

int slow = i, fast = i;Initialize pointers for cycle detection.

slow = nextIndex(nums, n, slow);Move slow pointer one step.

fast = nextIndex(nums, n, nextIndex(nums, n, fast));Move fast pointer two steps.

if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;Break if direction changes.

if (slow == fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited nodes to avoid reprocessing.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int nextIndex(vector<int>& nums, int n, int i) {
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            bool direction = nums[i] > 0;
            int slow = i, fast = i;
            while (true) {
                slow = nextIndex(nums, n, slow);
                fast = nextIndex(nums, n, nextIndex(nums, n, fast));
                if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;
                if (slow == fast) {
                    if (slow == nextIndex(nums, n, slow)) break;
                    return true;
                }
            }
            slow = i;
            while ((nums[slow] > 0) == direction) {
                int next = nextIndex(nums, n, slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

if (nums[i] == 0) continue;Skip indices already processed to save time.

bool direction = nums[i] > 0;Determine movement direction for cycle detection.

int slow = i, fast = i;Initialize pointers for cycle detection.

slow = nextIndex(nums, n, slow);Move slow pointer one step.

fast = nextIndex(nums, n, nextIndex(nums, n, fast));Move fast pointer two steps.

if ((nums[slow] > 0) != direction || (nums[fast] > 0) != direction) break;Break if direction changes.

if (slow == fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited nodes to avoid reprocessing.

var circularArrayLoop = function(nums) {
    const n = nums.length;
    const nextIndex = (i) => {
        let next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    };

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        const direction = nums[i] > 0;
        let slow = i, fast = i;
        while (true) {
            slow = nextIndex(slow);
            fast = nextIndex(nextIndex(fast));
            if ((nums[slow] > 0) !== direction || (nums[fast] > 0) !== direction) break;
            if (slow === fast) {
                if (slow === nextIndex(slow)) break;
                return true;
            }
        }
        slow = i;
        while ((nums[slow] > 0) === direction) {
            let next = nextIndex(slow);
            nums[slow] = 0;
            slow = next;
        }
    }
    return false;
};

// Test cases
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

if (nums[i] === 0) continue;Skip indices already processed to save time.

const direction = nums[i] > 0;Determine movement direction for cycle detection.

let slow = i, fast = i;Initialize pointers for cycle detection.

slow = nextIndex(slow);Move slow pointer one step.

fast = nextIndex(nextIndex(fast));Move fast pointer two steps.

if ((nums[slow] > 0) !== direction || (nums[fast] > 0) !== direction) break;Break if direction changes.

if (slow === fast) {Cycle detected if pointers meet.

nums[slow] = 0;Mark visited nodes to avoid reprocessing.

⏱

Complexity

TimeO(n)

SpaceO(1)

Same as previous approach but with minor practical speedups by early skipping.

💡 This approach is the best practical solution for large inputs.

Interview Verdict: Accepted

This is the recommended approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 The fast & slow pointer approach (Approach 2 or 3) is the best to implement in interviews due to optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Fast & Slow Pointer	O(n)	O(1)	No	N/A	Code this approach for optimal solution
3. Optimized Fast & Slow Pointer	O(n)	O(1)	No	N/A	Code this if you want minor practical improvements

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and definitions (cycle length, direction consistency).Step 2: Describe brute force simulation approach to show understanding.Step 3: Introduce fast & slow pointer technique for cycle detection.Step 4: Explain optimizations and marking visited elements.Step 5: Code the optimal solution and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of cycle detection, handling direction consistency, and ability to optimize from brute force to O(n) solution.

Common Follow-ups

• What if zero steps are allowed? → Need to handle zero carefully or disallow.
• Can you find the cycle start index? → Modify fast-slow pointer to find entry point.

💡 These follow-ups test your ability to adapt the solution to variations and deepen your understanding of cycle detection.

🔍

Pattern Recognition

When to Use

1) Problem involves cycle detection, 2) Input is circular or wraps around, 3) Movement defined by array values, 4) Direction consistency matters

Signature Phrases

circular arraycycle in arraydirection consistency

NOT This Pattern When

Problems involving simple sliding windows or sorting are different patterns.

Similar Problems

Linked List Cycle - classic fast-slow pointer cycle detectionHappy Number - cycle detection in number transformations

Practice

1. Given the following code snippet, what is the output when calling findDuplicate([3,1,3,4,2])?

easy

A. 3

B. 1

C. 4

D. 2

Solution

1. Step 1: Trace first phase to find intersection point

   Initialize slow=3, fast=3 (nums[0]=3). Iteration 1: slow=nums[3]=4, fast=nums[nums[3]]=nums[4]=2. Iteration 2: slow=nums[4]=2, fast=nums[nums[2]]=nums[3]=4. Iteration 3: slow=nums[2]=3, fast=nums[nums[4]]=nums[2]=3. They meet at 3.

2. Step 2: Trace second phase to find cycle entrance

   Reset slow=nums[0]=3. Since slow==fast==3, loop ends immediately. Return 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection returns duplicate 3 correctly [OK]

Hint: Cycle detection returns the duplicate value where pointers meet [OK]

Common Mistakes:

• Confusing slow and fast pointer updates
• Off-by-one errors in indexing
• Returning the wrong pointer value

2. You are given a singly linked list that may contain a cycle. The task is to find the node where the cycle begins, if any. Which of the following approaches guarantees finding the cycle's start node in O(n) time and O(1) space?

easy

A. Use two pointers moving at different speeds to detect the cycle and then find the cycle start by resetting one pointer to head.

B. Use a depth-first search to detect back edges and identify the cycle start.

C. Use a hash set to store visited nodes and return the first repeated node.

D. Use a greedy approach to jump nodes and check for cycles by comparing node values.

Solution

1. Step 1: Understand cycle detection with two pointers

   The fast and slow pointer technique detects a cycle by moving fast pointer twice as fast as slow pointer. If they meet, a cycle exists.

2. Step 2: Find cycle start by resetting one pointer

   After detection, reset one pointer to head and move both one step at a time until they meet again; this meeting point is the cycle start node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach finds cycle start in O(n) time and O(1) space [OK]

Hint: Two pointers detect and locate cycle start efficiently [OK]

Common Mistakes:

• Believing hash set is O(1) space
• Using DFS which is not suitable for linked lists
• Greedy jumps fail to detect cycles

3. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

4. Consider the following buggy code snippet for reorderList. Which line contains the subtle bug that can cause infinite loops or cycles when traversing the reordered list?

medium

A. Line with 'if left == right or left.next == right:' missing 'right.next = None' termination

B. Line with 'if not right: return' -- base case missing

C. Line with 'if stop: return' -- premature termination

D. Line with 'left = tmp' -- left pointer not updated correctly

Solution

1. Step 1: Identify termination condition

   The code must set right.next = None when left meets right or adjacent to avoid cycles.

2. Step 2: Locate missing termination

   The commented line misses 'right.next = None', causing the list to form cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing termination causes infinite traversal [OK]

Hint: Always terminate reordered list with null to avoid cycles [OK]

Common Mistakes:

• Forgetting to set right.next = null
• Misplacing stop flag
• Incorrect pointer updates

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow