How do you solve Longest Cycle in a Graph on LeetCode?

Longest Cycle in a Graph (LeetCode #2360) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Each node can only be part of one cycle, so we can track visited nodes efficiently.

What is the brute force solution for Longest Cycle in a Graph?

The brute force approach for Longest Cycle in a Graph is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves starting from each node and exploring all possible paths to find cycles. If a cycle is found, we measure its length. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Longest Cycle in a Graph?

Always clarify the problem statement and constraints before diving into coding. Think about edge cases, such as graphs with no cycles or all nodes leading to -1. Explain your thought process as you code; it shows your understanding and can help you catch mistakes.

What are common mistakes when solving Longest Cycle in a Graph?

Not properly tracking visited nodes can lead to incorrect cycle detection. Failing to reset the visited state after exploring a node can cause false positives.

#2360

Longest Cycle in a Graph

Hard

Depth-First SearchBreadth-First SearchGraph TheoryTopological SortDepth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a single pass through the graph with a depth-first search (DFS) while keeping track of visited nodes and their indices. This allows us to efficiently find cycles without redundant checks.

⚙️

Algorithm

3 steps

1Step 1: Initialize an array to track the visited state of each node and a map to store the index of each node in the current path.
2Step 2: For each node, if it hasn't been visited, perform a DFS to explore the graph.
3Step 3: During DFS, if a node is revisited, calculate the cycle length using the stored indices and update the maximum length.

solution.py22 lines

1def longestCycle(edges):
2    n = len(edges)
3    max_length = -1
4    visited = [0] * n
5
6    def dfs(node, index):
7        nonlocal max_length
8        if visited[node] == 0:
9            visited[node] = index
10            next_node = edges[node]
11            if next_node != -1:
12                dfs(next_node, index)
13            visited[node] = -1
14        elif visited[node] > 0:
15            cycle_length = index - visited[node]
16            max_length = max(max_length, cycle_length)
17
18    for i in range(n):
19        if visited[i] == 0:
20            dfs(i, i + 1)
21
22    return max_length

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(n) due to the visited array that tracks the state of each node.

1Each node can only be part of one cycle, so we can track visited nodes efficiently.
2Using a single pass with DFS allows us to avoid redundant checks and improve performance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.