# Detect Cycle in Sequence

> Follow the chain long enough and it might loop back.

Canonical URL: <https://datadriven.io/problems/detect_cycle_in_sequence>

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

You are given a list of integers where each value at index i is the next index to visit (or -1 to terminate). Starting from index 0, follow the chain and return True if you revisit any index, False otherwise. Out-of-range indices (including -1) count as termination, not a cycle.

## Worked solution and explanation

### Why this problem exists in real interviews

Cycle detection in linked structures is a fundamental graph problem. This tests whether you can use a **visited set** or **Floyd's cycle detection** to identify when a traversal revisits a node.

> **Trick to Solving**
>
> Use a set to track visited indices. At each step, check if the current index is already in the set before following the pointer. This gives O(n) time with O(n) space, which is perfectly acceptable here.

---

### Break down the requirements

#### Step 1: Start at index 0

The chain always begins at the first element of the array.

#### Step 2: Follow pointers until -1 or a revisit

Each value tells you the next index. Stop when you reach -1 (end of chain) or when you revisit an index.

#### Step 3: Return True if a revisit occurs

If the current index is already in the visited set, there is a cycle. If you reach -1, there is no cycle.

---

### The solution

**Visited-set traversal for cycle detection**

```python
def has_cycle(next_indices):
    if not next_indices:
        return False
    visited = set()
    idx = 0
    while idx != -1 and idx not in visited:
        visited.add(idx)
        if idx < 0 or idx >= len(next_indices):
            return False
        idx = next_indices[idx]
    return idx != -1
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the list length. Each index is visited at most once before detection.
> 
> **Space:** O(n) for the visited set in the worst case.

> **Interviewers Watch For**
>
> Whether you consider Floyd's tortoise-and-hare algorithm for O(1) space. For this problem the set approach is fine, but mentioning Floyd's shows depth of knowledge.

> **Common Pitfall**
>
> Not handling out-of-bounds indices. If a value points beyond the array, you should treat it as a non-cycle termination, similar to -1.

---

## Common follow-up questions

- Can you detect the cycle in O(1) extra space? _(Tests Floyd's cycle detection: slow pointer moves one step, fast pointer moves two.)_
- How would you return the index where the cycle begins? _(Tests the second phase of Floyd's algorithm or tracking the first repeated index.)_
- What if the chain can start from any index, not just 0? _(Tests running detection from every unvisited starting node, similar to connected components in a graph.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/detect_cycle_in_sequence)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.