HardDepth-First SearchBreadth-First SearchGraphTopological SortUpdated Sep 2026

2360. Longest Cycle in a Graph

Asked at Anduril

Difficulty

Hard

Time

O(n)

Space

O(n)

Pattern

Depth-First Search

Companies

1

Problem

You are given a directed graph with n nodes, numbered 0 to n-1. Each node has at most one outgoing edge. The array edges describes it: there is an edge from node i to node edges[i]. If edges[i] == -1, node i has no outgoing edge.

A cycle is a path that starts and ends at the same node. Return the length of the longest cycle in the graph, where length means the number of nodes on the cycle. If the graph has no cycle at all, return -1.

Because every node points to at most one other node, following edges from any node traces a single path. That path either stops at a node with no outgoing edge, or it eventually enters a loop.

One outgoing edge per node

edges3342301234edges[2]=4, edges[4]=3, edges[3]=2 — these three nodesform the longest cycle
Following edges from node 0 leads into the loop 2 → 4 → 3 → 2, which has length 3.

Constraints

  • ●n == edges.length
  • ●2 <= n <= 10^5
  • ●-1 <= edges[i] < n
  • ●edges[i] != i

Examples

Example 1
Inputedges = [3,3,4,2,3]
Output3
WhyNode 2 points to 4, node 4 points to 3, and node 3 points back to 2. That loop visits 3 nodes, and no other cycle is longer, so the answer is 3.
Example 2
Inputedges = [2,-1,3,1]
Output-1
WhyNode 0 goes to 2, node 2 goes to 3, node 3 goes to 1, and node 1 has no outgoing edge. Every path dies out, so there is no cycle.

Asked At

1 companies
CompanyDifficulty
AndurilHardView all Anduril questions →

How to Think About It

1

With at most one outgoing edge per node, following edges from any node traces a single path that either stops at -1 or eventually loops.

2

Key insight: walk from each unvisited node, stamping every node with a global increasing time. Remember the time at which this walk started.

3

If the walk reaches a node stamped during the current walk (its stamp is at least the start time), you found a cycle of length currentTime - stamp[node].

4

If it reaches a node stamped by an earlier walk, stop — that region has already been fully explored.

5

Each node is stamped once, so the total work is O(n).

Optimal Approach

Step 1: stamp = [0] * n, time = 1, best = -1.
Step 2: For each node s with stamp[s] == 0:
start = time, u = s.
While u != -1 and stamp[u] == 0: stamp[u] = time, time += 1, u = edges[u].
If u != -1 and stamp[u] >= start: best = max(best, time - stamp[u]).
Step 3: Return best.

Time: O(n). Space: O(n).

Stamp each node with a global time

stamp1234501234Walk from node 0: stamps 1,2,3,4,5 land on nodes0,3,2,4,1 in that orderstampcycle1234501234Node 2 already has stamp 3, which is >= start=1, so acycle was foundlength = time − stamp[u]= 6 − 3 = 3
A node stamped at or after the start of the current walk means we closed a loop during this walk.
ComplexityTime O(n)Space O(n)Each node is stamped exactly once, so the total walking work is linear; the stamp array costs O(n) memory.

What Trips People Up in Real Interviews

1

Using a general cycle-detection DFS with recursion — correct but heavier, and it can overflow the stack on long chains.

2

Counting a cycle when the walk runs into a node visited by a previous walk. Only nodes stamped in the current walk form a new cycle.

3

Resetting visited marks between starting nodes, which makes the algorithm quadratic.

4

Forgetting nodes with edges[i] == -1.

Solution Code

O(n) time
def longestCycle(edges):
    n = len(edges)
    stamp = [0] * n
    time = 1
    best = -1
    for s in range(n):
        if stamp[s]:
            continue
        start = time
        u = s
        while u != -1 and stamp[u] == 0:
            stamp[u] = time
            time += 1
            u = edges[u]
        if u != -1 and stamp[u] >= start:
            best = max(best, time - stamp[u])
    return best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest Cycle in a Graph problem?

Longest Cycle in a Graph gives you a directed graph where every node has at most one outgoing edge (`edges[i]`, or -1), and asks for the length of the longest cycle, or -1 if none exists. Because each node has a single successor, you can walk paths directly and detect cycles with visit timestamps.

How do you solve Longest Cycle in a Graph?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Cycle in a Graph?

Longest Cycle in a Graph is asked at Anduril. It is a hard difficulty problem.

What are common mistakes on Longest Cycle in a Graph?
  • Using a general cycle-detection DFS with recursion — correct but heavier, and it can overflow the stack on long chains.
  • Counting a cycle when the walk runs into a node visited by a previous walk. Only nodes stamped in the current walk form a new cycle.
  • Resetting visited marks between starting nodes, which makes the algorithm quadratic.
  • Forgetting nodes with `edges[i] == -1`.