Longest Cycle in a Graph

Hard

#2149Time: 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).1 company

Algorithms

Depth-First Search Breadth-First Search Topological Sort

Data structures

Graph

Companies

Juspay

Prompt

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.length
2 <= n <= 10⁵
-1 <= edges[i] < n
edges[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 visited array of size n to track nodes that have been part of any completed traversal, initialized to false.
Iterate through each node i from 0 to n-1.
If visited[i] is false:
- Start a new traversal from i.
- Use a HashMap, distMap, to store (node, distance) for the current path only.
- Initialize dist = 0 and currentNode = i.
- Traverse the path as long as currentNode is valid:
  - If currentNode is in distMap, a cycle is found. Calculate its length (dist - distMap.get(currentNode)), update maxLength, 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) to distMap.
  - Move to the next node: currentNode = edges[currentNode] and increment dist.
- After the traversal from i is complete (due to cycle, visited node, or -1), mark all nodes in distMap as globally visited by setting visited[node] = true.
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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int longestCycle(int[] edges) {6        int n = edges.length;7        int maxLength = -1;8        boolean[] visited = new boolean[n];9 10        for (int i = 0; i < n; i++) {11            if (!visited[i]) {12                Map<Integer, Integer> distMap = new HashMap<>();13                int dist = 0;14                int currentNode = i;15 16                while (currentNode != -1) {17                    if (distMap.containsKey(currentNode)) {18                        int cycleLength = dist - distMap.get(currentNode);19                        maxLength = Math.max(maxLength, cycleLength);20                        break; 21                    }22                    if (visited[currentNode]) {23                        // Path merges into an already processed component.24                        break;25                    }26                    27                    distMap.put(currentNode, dist);28                    currentNode = edges[currentNode];29                    dist++;30                }31                32                // Mark all nodes in the current path as visited to avoid re-processing.33                for (int node : distMap.keySet()) {34                    visited[node] = true;35                }36            }37        }38        return maxLength;39    }40}

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.

This approach involves iterating through every node in the graph and, for each one, starting a new traversal to detect a cycle. It keeps track of the path taken from the starting node. If a node is encountered that has already been seen in the current path, a cycle is detected, and its length is calculated. This process is repeated for all nodes to ensure the longest cycle is found.

Algorithm

Initialize a variable maxLength to -1.
Iterate through each node i from 0 to n-1 to use as a starting point for a traversal.
For each starting node i:
- Create a HashMap called pathMap to store visited nodes and their distances in the current traversal.
- Initialize distance = 0 and currentNode = i.
- Start a while loop that continues as long as currentNode is valid (not -1).
- Inside the loop, check if currentNode is already in pathMap.
  - If yes, a cycle is found. Calculate its length as distance - pathMap.get(currentNode). Update maxLength if this cycle is longer. Then, break the inner loop.
  - If no, add currentNode and its distance to pathMap.
- Move to the next node by setting currentNode = edges[currentNode] and increment distance.
After checking all nodes as starting points, return maxLength.

Walkthrough

The brute-force algorithm systematically checks for cycles starting from every single node. For each node i, it traces the path of outgoing edges, recording each visited node and its distance from i in a hash map. If the traversal encounters a node that's already in the hash map for the current path, it signifies a cycle. The length of the cycle is the difference between the current distance and the distance stored when the node was first visited. The maximum length found across all starting nodes is the result.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int longestCycle(int[] edges) {6        int n = edges.length;7        int maxLength = -1;8 9        for (int i = 0; i < n; i++) {10            // For each starting node, we trace its path.11            Map<Integer, Integer> pathMap = new HashMap<>();12            int dist = 0;13            int currentNode = i;14 15            while (currentNode != -1) {16                if (pathMap.containsKey(currentNode)) {17                    // Cycle detected.18                    int cycleLength = dist - pathMap.get(currentNode);19                    maxLength = Math.max(maxLength, cycleLength);20                    break;21                }22                23                pathMap.put(currentNode, dist);24                currentNode = edges[currentNode];25                dist++;26            }27        }28        return maxLength;29    }30}

Complexity

Time

O(N^2), where N is the number of nodes. The outer loop runs N times. For each iteration, the inner `while` loop can traverse up to N nodes in the worst case (e.g., a graph that is one long cycle).

Space

O(N), where N is the number of nodes. In each iteration of the outer loop, the `pathMap` can store up to N entries in the worst-case scenario of a single path or cycle involving all nodes.

Trade-offs

Pros

Simple to conceptualize and implement.
Guaranteed to find the correct longest cycle length.

Cons

Highly inefficient due to redundant computations. The same paths and cycles are traversed multiple times from different starting nodes.
For larger graphs, this approach will be too slow and will likely exceed the time limit on platforms like LeetCode.

Solutions

Solution

1class Solution {2public3  int longestCycle(int[] edges) {4    int n = edges.length;5    boolean[] vis = new boolean[n];6    int ans = -1;7    for (int i = 0; i < n; ++i) {8      if (vis[i]) {9        continue;10      }11      int j = i;12      List<Integer> cycle = new ArrayList<>();13      for (; j != -1 && !vis[j]; j = edges[j]) {14        vis[j] = true;15        cycle.add(j);16      }17      if (j == -1) {18        continue;19      }20      for (int k = 0; k < cycle.size(); ++k) {21        if (cycle.get(k) == j) {22          ans = Math.max(ans, cycle.size() - k);23          break;24        }25      }26    }27    return ans;28  }29}

1class Solution:2    def longestCycle(self, edges: List[int]) -> int: n = len(edges) vis = [False] * n ans = - 1 for i in range(n): if vis[i]: continue j = i cycle = [] while j != - 1 and not vis[j]: vis[j] = True cycle . append(j) j = edges[j] if j == - 1: continue m = len(cycle) k = next((k for k in range(m) if cycle[k] == j), inf) ans = max(ans, m - k) return ans

1class Solution {2public:3  int longestCycle(vector<int> &edges) {4    int n = edges.size();5    vector<bool> vis(n);6    int ans = -1;7    for (int i = 0; i < n; ++i) {8      if (vis[i]) {9        continue;10      }11      int j = i;12      vector<int> cycle;13      for (; j != -1 && !vis[j]; j = edges[j]) {14        vis[j] = true;15        cycle.push_back(j);16      }17      if (j == -1) {18        continue;19      }20      for (int k = 0; k < cycle.size(); ++k) {21        if (cycle[k] == j) {22          ans = max(ans, (int)cycle.size() - k);23          break;24        }25      }26    }27    return ans;28  }29};

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.

← Previous

Previous problem

Next problem