Longest Cycle in a Graph
HardPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This optimized approach avoids re-processing nodes by using a global visited array. It iterates through each node, and if a node hasn't been visited yet, it starts a traversal (akin to a Depth First Search). During the traversal, it keeps track of the current path and distances. If a cycle is found, its length is calculated. If the path leads to an already visited node, the traversal stops, as that part of the graph has been checked. This ensures each node is processed only once.
Algorithm
- Initialize
maxLength = -1. - Create a global boolean
visitedarray of sizento track nodes that have been part of any completed traversal, initialized tofalse. - Iterate through each node
ifrom0ton-1. - If
visited[i]isfalse:- Start a new traversal from
i. - Use a
HashMap,distMap, to store(node, distance)for the current path only. - Initialize
dist = 0andcurrentNode = i. - Traverse the path as long as
currentNodeis valid:- If
currentNodeis indistMap, a cycle is found. Calculate its length (dist - distMap.get(currentNode)), updatemaxLength, and break the inner traversal. - If
visited[currentNode]is true, the path has merged into an already explored component. No new cycle can be found, so break the inner traversal. - Otherwise, add
(currentNode, dist)todistMap. - Move to the next node:
currentNode = edges[currentNode]and incrementdist.
- If
- After the traversal from
iis complete (due to cycle, visited node, or -1), mark all nodes indistMapas globally visited by settingvisited[node] = true.
- Start a new traversal from
- Return
maxLength.
Walkthrough
This method is an efficient, DFS-like traversal. We maintain a global visited array to ensure that each node is processed at most once. We iterate from node 0 to n-1. If a node i has not been visited, we begin a traversal. We use a local HashMap to store the nodes in the current path and their distances from the starting node i.
If during this traversal we encounter a node that is already in our local map, we've found a cycle. We calculate its length and update our maximum. If we encounter a node that is in the global visited array, it means we've merged with a path that has already been fully explored, so we can stop the current traversal. After a traversal from a starting node i concludes, we mark all nodes visited in that path in the global visited array to prevent redundant work.
import java.util.HashMap;import java.util.Map; class Solution { public int longestCycle(int[] edges) { int n = edges.length; int maxLength = -1; boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i]) { Map<Integer, Integer> distMap = new HashMap<>(); int dist = 0; int currentNode = i; while (currentNode != -1) { if (distMap.containsKey(currentNode)) { int cycleLength = dist - distMap.get(currentNode); maxLength = Math.max(maxLength, cycleLength); break; } if (visited[currentNode]) { // Path merges into an already processed component. break; } distMap.put(currentNode, dist); currentNode = edges[currentNode]; dist++; } // Mark all nodes in the current path as visited to avoid re-processing. for (int node : distMap.keySet()) { visited[node] = true; } } } return maxLength; }}Complexity
Time
O(N), where N is the number of nodes. Each node is visited a constant number of times. The outer loop runs N times, but the inner `while` loop's work is amortized across all nodes, as each node is marked `visited` after being processed once.
Space
O(N), where N is the number of nodes. This is for the `visited` array and the `distMap`. In the worst case, `distMap` can hold up to N nodes (a single path or cycle).
Trade-offs
Pros
Highly efficient, with a linear time complexity.
Avoids redundant computations by ensuring each node is processed only once.
Optimal solution for the given constraints.
Cons
Slightly more complex to implement than the brute-force approach due to the need to manage both a global visited state and a local path state.
Solutions
Solution
class Solution {public int longestCycle(int[] edges) { int n = edges.length; boolean[] vis = new boolean[n]; int ans = -1; for (int i = 0; i < n; ++i) { if (vis[i]) { continue; } int j = i; List<Integer> cycle = new ArrayList<>(); for (; j != -1 && !vis[j]; j = edges[j]) { vis[j] = true; cycle.add(j); } if (j == -1) { continue; } for (int k = 0; k < cycle.size(); ++k) { if (cycle.get(k) == j) { ans = Math.max(ans, cycle.size() - k); break; } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.