HardDepth-First SearchGraphTopological Sort

Longest Cycle in a Graph

1 approach, code in all languages

You are given a directed graph with n nodes labeled 0 to n - 1, described by an array edges of length n. Each node has at most one outgoing edge: edges[i] is the node that i points to, or -1 when node i has no outgoing edge.

Return the length of the longest cycle in the graph. If the graph contains no cycle at all, return -1.

Because every node has out-degree at most one, the paths form simple chains that either terminate at a -1 or loop back to a previously seen node.

Example 1

Input: edges = [3,3,4,2,3]

Output: 3

Following edges from node 2 gives 2 -> 4 -> 3 -> 2, a cycle of length 3, which is the longest one present.

Example 2

Input: edges = [2,-1,3,1]

Output: -1

The chain 0 -> 2 -> 3 -> 1 ends at node 1, whose edge is -1. No path loops back, so there is no cycle.

Constraints

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

Functional-Graph Walk with Visit Timestamps

Walk each chain once, stamping a global time and the time each walk started, to measure any loop instantly.

Loading animation…

Intuition

Since each node has at most one outgoing edge, we can simply follow the single chain from any starting node without branching. We keep a global clock that only moves forward and record the exact time each node is first visited. When we start a fresh walk we remember the clock value at that moment. If the walk re-enters a node whose visit time is at least the walk's start time, that node was seen during this very walk, so we just closed a cycle. The cycle length is the difference between the current clock and the visit time of that re-entered node. Nodes touched by earlier walks are already resolved, so stopping at them costs nothing and guarantees each node is processed once.

Algorithm walkthrough

1Keep a global clock time starting at 1, a visited flag per node, and a visitTime per node.
2For each unvisited start node, record walkStart = time and follow the outgoing edges.
3While the current node is not -1 and not yet visited, mark it visited, set visitTime to the clock, advance the clock, and step to edges[node].
4The walk stops at a dead end (-1) or at an already visited node.
5If it stopped on a node whose visitTime is at least walkStart, a cycle formed; its length is time minus that node's visitTime.
6Track the maximum cycle length across all walks and return it, or -1 if none was found.

Implementation

from typing import List

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        visit_time = [0] * n
        visited = [False] * n
        time = 1
        answer = -1

        for i in range(n):
            if visited[i]:
                continue
            walk_start = time
            node = i
            while node != -1 and not visited[node]:
                visited[node] = True
                visit_time[node] = time
                time += 1
                node = edges[node]
            if node != -1 and visit_time[node] >= walk_start:
                answer = max(answer, time - visit_time[node])

        return answer

Time

O(n)

Space

O(n)

Every node is stamped once and never revisited, so the total work is linear. The two arrays use O(n) space.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI