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. Consider the following code that detects a cycle by marking nodes as visited. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2), what is the output of hasCycle(node1)?

easy

A. true

B. false

C. null

D. Runtime error due to infinite loop

Solution

1. Step 1: Trace the traversal and marking of nodes

   Start at node1 (visited=false), mark visited=true, move to node2. Repeat for node2 and node3. When reaching node4, mark visited=true and move to node2 again, which is already visited.

2. Step 2: Detect cycle when revisiting node2

   Since node2.visited is true, the function returns true indicating a cycle.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detected correctly by visited flag [OK]

Hint: Cycle detected when revisiting a marked node [OK]

Common Mistakes:

• Assuming no cycle due to missing pointer update
• Confusing return values

2. Examine the following buggy code snippet for deleting N nodes after skipping M nodes in a linked list. Identify the line that contains the subtle bug causing potential runtime errors or incorrect output.

def delete_n_after_m_buggy(head, M, N):
    current = head
    while current:
        for _ in range(1, M):
            current = current.next
        if current is null:
            break
        temp = current.next
        for _ in range(N):
            if temp is null:
                break
            temp = temp.next
        current.next = temp
        current = temp
    return head

medium

A. Line 13: current.next = temp

B. Line 6: if current is null: break

C. Line 10: for _ in range(N): if temp is null: break

D. Line 4: for _ in range(1, M): current = current.next

Solution

1. Step 1: Analyze pointer movement in skipping loop

   The loop moves current forward M-1 times without checking if current is null before moving, risking NoneType attribute errors.

2. Step 2: Identify missing null check

   Without checking current before current = current.next, code may dereference null, causing runtime error.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding null check inside skipping loop prevents runtime errors [OK]

Hint: Always check for null before moving pointers in loops [OK]

Common Mistakes:

• Missing null checks before pointer moves
• Incorrectly updating next pointers causing cycles
• Assuming list length always sufficient

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

4. What is the space complexity of the recursive reorderList implementation shown below, considering a linked list of length n?

medium

A. O(log n) -- recursion divides list in halves

B. O(1) -- only constant extra pointers used

C. O(n) -- recursion stack grows linearly with list length

D. O(n^2) -- nested recursive calls cause quadratic space

Solution

1. Step 1: Analyze recursion depth

   Each recursive call moves one node forward, so recursion depth is n.

2. Step 2: Determine space usage

   Each call adds a stack frame, so total auxiliary space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack grows linearly with input size [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming recursion is O(1) space
• Confusing recursion with divide-and-conquer
• Thinking nested calls multiply space

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