Longest Cycle in a Graph solution and explanation
Google
9 more videos on this problem
Longest Cycle in a Graph | Leetcode - 2360 | DFS | Explanation ➕ Live Coding TrashcodestorywithMIK · 32:26 · 15K views
Leetcode 2360. Longest Cycle in a Graph | Weekly Contest 304. Hard Problem 4Code with Alisha · 13:46 · 11K views
2360. Longest Cycle in a Graph || Leetcode Weekly Contest 304Bro Coders · 9:59 · 4K views
Leetcode 2360 Longest Cycle in a Graph | Easy Peasy GraphsCoding Decoded · 7:41 · 3K views
Daily Leetcode #1090: Mar 26, 2023 - 2360. Longest Cycle in a GraphProgramming Live with Larry · 14:40 · 960 views
2360 || Longest Cycle in a Graph || C++ || Leetcode Daily ChallengeCodeFreaks · 21:49 · 723 views
LeetCode 2360 - Longest Cycle in a Graph [Daily Challenge]Code with Carter · 15:36 · 660 views
2360. Longest Cycle in a Graph | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 10:01 · 639 views
2360. Longest Cycle in a Graph (Leetcode Hard)Programming Live with Larry · 32:52 · 597 views
Leetcode 2360 Longest Cycle in a Graph (Java)TheAnalyticGuy · 10:31 · 546 views
The problem
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.
The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1.
Return the length of the longest cycle in the graph. If no cycle exists, return -1.
A cycle is a path that starts and ends at the same node.
Example 1:
Input: edges = [3,3,4,2,3] Output: 3 Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2. The length of this cycle is 3, so 3 is returned.
Example 2:
Input: edges = [2,-1,3,1] Output: -1 Explanation: There are no cycles in this graph.
Constraints:
n == edges.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i
Approach overview
Problem Overview: You are given a directed graph where each node has at most one outgoing edge. The task is to find the length of the longest cycle in the graph. If no cycle exists, return -1. Because each node points to at most one neighbor, the graph behaves like multiple chains that may eventually form cycles.
Approach 1: Brute Force Traversal from Every Node (O(n^2) time, O(n) space)
Start a traversal from every node and follow outgoing edges until you either reach a visited node or a dead end (-1). Maintain a map or array storing the step index when each node was first seen in the current traversal. If you revisit a node from the same traversal path, a cycle exists and its length equals the difference between the current step and the stored step. Reset tracking for the next start node. This works but repeats large portions of the graph many times.
Approach 2: DFS with Cycle Detection (O(n) time, O(n) space)
Use Depth-First Search with visitation states to detect cycles efficiently. Track three states for each node: unvisited, visiting, and processed. While performing DFS, store the depth or timestamp when you first enter each node. If you reach a node currently marked visiting, you discovered a cycle and its length equals currentDepth - entryDepth[node]. Mark nodes as processed after finishing their path so they are never revisited again. Because every node has at most one outgoing edge, each node is explored once, giving linear time.
Approach 3: Topological Pruning + Cycle Counting (O(n) time, O(n) space)
Another efficient strategy removes nodes that cannot be part of any cycle. Compute indegree for each node in the graph. Push all nodes with indegree 0 into a queue and repeatedly remove them, updating the indegree of their neighbors. This topological sort style pruning eliminates all acyclic chains. The remaining nodes must belong to cycles. Traverse each remaining component and count its cycle length, keeping the maximum.
Recommended for interviews: DFS with cycle detection is the most common solution. It demonstrates strong understanding of graph traversal, visitation states, and cycle detection. The topological pruning approach is also optimal and shows deeper graph reasoning. Brute force helps explain the intuition but does not scale to large inputs.
Approach 1: DFS with Cycle Detection
This approach involves using Depth First Search (DFS) to traverse the graph nodes by starting at each unvisited node. As we explore, we track the nodes in the current path to detect cycles. Whenever we reach a previously visited node that is part of the current path, a cycle is detected, and its length is computed. We keep track of the longest cycle found during the traversal.
def dfs(node, edges, visited, recStack, pathLength):
if node == -1:
return -1
if recStack[node]:
return pathLength - visited[node]
if visited[node] != -1:
return -1
visited[node] = pathLength
recStack[node] = True
pathLength += 1
cycleLength = dfs(edges[node], edges, visited, recStack, pathLength)
recStack[node] = False
return cycleLength
def longestCycle(edges):
maxLength = -1
n = len(edges)
visited = [-1] * n
recStack = [False] * n
for node in range(n):
if visited[node] == -1:
pathLength = 0
cycleLength = dfs(node, edges, visited, recStack, pathLength)
maxLength = max(maxLength, cycleLength)
return maxLength
edges = [3, 3, 4, 2, 3]
print(longestCycle(edges))import java.util.*;
public class LongestCycleGraph {
private static int dfs(int node, int[] edges, int[] visited, boolean[] recStack, int pathLength) {
if (node == -1) return -1;
if (recStack[node]) return pathLength - visited[node];
if (visited[node] != -1) return -1;
visited[node] = pathLength;
recStack[node] = true;
pathLength++;
int cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
recStack[node] = false;
return cycleLength;
}
public static int longestCycle(int[] edges) {
int n = edges.length;
int maxLength = -1;
int[] visited = new int[n];
Arrays.fill(visited, -1);
boolean[] recStack = new boolean[n];
for (int i = 0; i < n; i++) {
if (visited[i] == -1) {
int pathLength = 0;
int cycleLength = dfs(i, edges, visited, recStack, pathLength);
maxLength = Math.max(maxLength, cycleLength);
}
}
return maxLength;
}
public static void main(String[] args) {
int[] edges = {3, 3, 4, 2, 3};
System.out.println(longestCycle(edges));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dfs(int node, vector<int>& edges, vector<int>& visited, vector<int>& recStack, int& pathLength) {
if (node == -1) return -1;
if (recStack[node]) return pathLength - visited[node];
if (visited[node] != -1) return -1;
visited[node] = pathLength;
recStack[node] = 1;
pathLength++;
int cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
recStack[node] = 0;
pathLength--;
return cycleLength;
}
int longestCycle(vector<int>& edges) {
int maxLength = -1;
int n = edges.size();
vector<int> visited(n, -1);
vector<int> recStack(n, 0);
for (int i = 0; i < n; ++i) {
if (visited[i] == -1) {
int pathLength = 0;
int cycleLength = dfs(i, edges, visited, recStack, pathLength);
if (cycleLength > maxLength) maxLength = cycleLength;
}
}
return maxLength;
}
int main() {
vector<int> edges = {3, 3, 4, 2, 3};
cout << longestCycle(edges) << endl;
return 0;
}function dfs(node, edges, visited, recStack, pathLength) {
if (node === -1) return -1;
if (recStack[node]) return pathLength - visited[node];
if (visited[node] !== -1) return -1;
visited[node] = pathLength;
recStack[node] = true;
pathLength++;
const cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
recStack[node] = false;
return cycleLength;
}
function longestCycle(edges) {
let maxLength = -1;
const n = edges.length;
const visited = Array(n).fill(-1);
const recStack = Array(n).fill(false);
for (let i = 0; i < n; i++) {
if (visited[i] === -1) {
let pathLength = 0;
const cycleLength = dfs(i, edges, visited, recStack, pathLength);
maxLength = Math.max(maxLength, cycleLength);
}
}
return maxLength;
}
const edges = [3, 3, 4, 2, 3];
console.log(longestCycle(edges));#include <stdio.h>
#include <stdlib.h>
int dfs(int node, int *edges, int *visited, int *recStack, int *pathLength) {
if (node == -1) return -1;
if (recStack[node]) return *pathLength - visited[node];
if (visited[node] != -1) return -1;
visited[node] = *pathLength;
recStack[node] = 1;
(*pathLength)++;
int cycleLength = dfs(edges[node], edges, visited, recStack, pathLength);
recStack[node] = 0;
(*pathLength)--;
return cycleLength;
}
int longestCycle(int* edges, int edgesSize) {
int maxLength = -1;
int *visited = (int*)malloc(sizeof(int) * edgesSize);
int *recStack = (int*)calloc(edgesSize, sizeof(int));
for (int i = 0; i < edgesSize; ++i) visited[i] = -1;
for (int i = 0; i < edgesSize; ++i) {
if (visited[i] == -1) {
int pathLength = 0;
int cycleLength = dfs(i, edges, visited, recStack, &pathLength);
if (cycleLength > maxLength) maxLength = cycleLength;
}
}
free(visited);
free(recStack);
return maxLength;
}
int main() {
int edges[] = {3, 3, 4, 2, 3};
int edgesSize = 5;
printf("%d\n", longestCycle(edges, edgesSize));
return 0;
}using System;
public class LongestCycleGraph {
private static int Dfs(int node, int[] edges, int[] visited, bool[] recStack, int pathLength) {
if (node == -1) return -1;
if (recStack[node]) return pathLength - visited[node];
if (visited[node] != -1) return -1;
visited[node] = pathLength;
recStack[node] = true;
pathLength++;
int cycleLength = Dfs(edges[node], edges, visited, recStack, pathLength);
recStack[node] = false;
return cycleLength;
}
public static int LongestCycle(int[] edges) {
int n = edges.Length;
int maxLength = -1;
int[] visited = new int[n];
Array.Fill(visited, -1);
bool[] recStack = new bool[n];
for (int i = 0; i < n; i++) {
if (visited[i] == -1) {
int pathLength = 0;
int cycleLength = Dfs(i, edges, visited, recStack, pathLength);
maxLength = Math.Max(maxLength, cycleLength);
}
}
return maxLength;
}
public static void Main() {
int[] edges = {3, 3, 4, 2, 3};
Console.WriteLine(LongestCycle(edges));
}
}The Python solution effectively uses recursive DFS exploration with lists for tracking visited nodes and maintaining the recursion path stack. The cycle is determined when a node is revisited in the current path, returning the cycle's length.
Time Complexity: O(n), as all nodes and edges are explored.
Space Complexity: O(n), since lists are used to manage path and visited nodes.
Approach 2: Traverse Starting Points
We can traverse each node in the range [0,..,n-1]. If a node has not been visited, we start from this node and search for adjacent nodes until we encounter a cycle or a node that has already been visited. If we encounter a cycle, we update the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes.
Similar problems:
function longestCycle(edges: number[]): number {
const n = edges.length;
const vis: boolean[] = Array(n).fill(false);
let ans = -1;
for (let i = 0; i < n; ++i) {
if (vis[i]) {
continue;
}
let j = i;
const cycle: number[] = [];
for (; j !== -1 && !vis[j]; j = edges[j]) {
vis[j] = true;
cycle.push(j);
}
if (j === -1) {
continue;
}
for (let k = 0; k < cycle.length; ++k) {
if (cycle[k] === j) {
ans = Math.max(ans, cycle.length - k);
break;
}
}
}
return ans;
}func longestCycle(edges []int) int {
vis := make([]bool, len(edges))
ans := -1
for i := range edges {
if vis[i] {
continue
}
j := i
cycle := []int{}
for ; j != -1 && !vis[j]; j = edges[j] {
vis[j] = true
cycle = append(cycle, j)
}
if j == -1 {
continue
}
for k := range cycle {
if cycle[k] == j {
ans = max(ans, len(cycle)-k)
break
}
}
}
return ans
}impl Solution {
pub fn longest_cycle(edges: Vec<i32>) -> i32 {
let n = edges.len();
let mut vis = vec![false; n];
let mut ans = -1;
for i in 0..n {
if vis[i] {
continue;
}
let mut j = i as i32;
let mut cycle = Vec::new();
while j != -1 && !vis[j as usize] {
vis[j as usize] = true;
cycle.push(j);
j = edges[j as usize];
}
if j == -1 {
continue;
}
for k in 0..cycle.len() {
if cycle[k] == j {
ans = ans.max((cycle.len() - k) as i32);
break;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| DFS with Cycle Detection | Time Complexity: O(n), as all nodes and edges are explored. |
| Traverse Starting Points | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Traversal from Each Node | O(n^2) | O(n) | Useful for understanding cycle detection before optimizing |
| DFS with Cycle Detection | O(n) | O(n) | General optimal solution; common interview expectation |
| Topological Pruning + Cycle Counting | O(n) | O(n) | When identifying cycle-only components after removing acyclic nodes |
Frequently asked questions
Is Longest Cycle in a Graph easy or hard?
Longest Cycle in a Graph is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the graph structure where each node has only one outgoing edge and applying an efficient cycle detection strategy that runs in O(n) time.
Longest Cycle in a Graph Python/Java solution
Python and Java implementations typically use arrays to track visit states and entry depths during DFS. The algorithm iterates through each node, launches DFS for unvisited nodes, and updates the maximum cycle length whenever a back-edge to a visiting node is detected.
How to solve Longest Cycle in a Graph in O(n)?
Use DFS or topological pruning. In the DFS approach, maintain a recursion stack or visiting state and store entry depth for each node. When DFS revisits a node in the current path, compute the cycle length using the difference between current depth and stored depth. Since each node is processed once, the algorithm runs in linear time.
What is the best approach for Longest Cycle in a Graph?
The most common solution uses DFS with cycle detection. Track visitation states (unvisited, visiting, processed) and record the depth when entering each node. If DFS reaches a node already in the visiting state, a cycle exists and its length can be computed using the stored depth. This approach runs in O(n) time and O(n) space.
Is Longest Cycle in a Graph asked at Google/Amazon/Meta?
Graph cycle detection problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving detecting cycles, finding cycle length, or pruning acyclic nodes are common in graph-focused interview rounds.
What data structure is used in Longest Cycle in a Graph?
The solution uses arrays or lists to represent the graph edges, along with additional arrays for visitation states and depth tracking. DFS traversal or a queue for topological pruning are the primary techniques used to detect and measure cycles.
What is the time complexity of Longest Cycle in a Graph?
The optimal solution runs in O(n) time where n is the number of nodes. Each node is visited at most once because the graph has at most one outgoing edge per node. Space complexity is O(n) for the visitation state and depth tracking arrays.