LeetCode 2360 - Longest Cycle in a Graph

This problem gives us a directed graph represented by an array called edges. The graph contains n nodes labeled from 0 to n - 1. Each node has at most one outgoing edge.

leetcodeharddepth-first-searchbreadth-first-searchgraph-theorytopological-sort

LeetCode Problem 2360

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a directed graph represented by an array called edges. The graph contains n nodes labeled from 0 to n - 1. Each node has at most one outgoing edge.

The meaning of the array is straightforward:

  • If edges[i] = j, there is a directed edge from node i to node j
  • If edges[i] = -1, node i has no outgoing edge

The task is to find the length of the longest cycle in the graph. If the graph contains no cycles, we return -1.

A cycle occurs when following directed edges eventually brings us back to a previously visited node in the current traversal path. For example:

2 -> 4 -> 3 -> 2

This is a cycle of length 3.

An important characteristic of this graph is that every node has at most one outgoing edge. This dramatically simplifies the structure compared to a general directed graph. Each connected component behaves like a chain that may eventually terminate or enter a cycle.

The constraints are large:

  • n can be as large as 100000
  • A quadratic solution would be far too slow
  • We need an algorithm close to linear time

The problem also guarantees:

  • edges[i] != i, so there are no self-loops
  • Outgoing edges are valid node indices or -1

Several edge cases are important:

  • Graphs with no cycles at all
  • Multiple disconnected components
  • Multiple cycles where we must choose the longest
  • Long chains leading into a cycle
  • Nodes already processed from previous traversals
  • Very large inputs where repeated work would cause time limit issues

Because each node has at most one outgoing edge, we can process the graph efficiently by tracking traversal order and detecting when we revisit a node within the same traversal.

Approaches

Brute Force Approach

A brute-force solution would start a traversal from every node independently.

For each starting node:

  1. Follow outgoing edges one by one
  2. Keep track of visited nodes for that traversal
  3. If we revisit a node already seen in the current path, we found a cycle
  4. Compute the cycle length
  5. Repeat for every node

This works because eventually one of two things happens:

  • We reach -1, meaning no cycle exists in that path
  • We revisit a node, meaning a cycle exists

The problem with this approach is repeated work. Consider a long chain of nodes. If we start from every node separately, we may traverse the same path many times.

In the worst case, each traversal could take O(n) time, and we perform it for all n nodes. This leads to O(n²) complexity, which is too slow for n = 100000.

Optimal Approach

The key insight is that once a node has been fully processed, we never need to process it again.

Because every node has at most one outgoing edge, traversals are deterministic. From any node, there is only one possible path forward.

We can exploit this by maintaining:

  • A global visited array to avoid reprocessing nodes
  • A map storing the step index of nodes visited during the current traversal

When we encounter a node already seen in the current traversal, we immediately know a cycle exists. The cycle length is:

current_step - first_seen_step

This approach ensures every node is processed at most once globally, giving us linear time complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeats traversal work from many starting nodes
Optimal O(n) O(n) Each node processed at most once

Algorithm Walkthrough

  1. Create a global visited array of size n, initialized to False.

This array tracks whether a node has already been fully processed in any traversal. Once a node is marked visited, we never need to start from it again. 2. Initialize longest_cycle to -1.

This stores the maximum cycle length found so far. If no cycles exist, it remains -1. 3. Iterate through every node from 0 to n - 1.

For each node:

  • If it is already globally visited, skip it
  • Otherwise, begin a fresh traversal from that node
  1. For each traversal, create a dictionary called distance.

This dictionary maps:

node -> step index

It records when each node was first visited during the current traversal only. 5. Start traversing forward along outgoing edges.

At each step:

  • Mark the node as globally visited
  • Record its step number in distance
  • Move to the next node using edges[current]
  1. Continue traversal until one of three conditions occurs.

Case 1:

current == -1

This means the path terminates and no cycle exists.

Case 2:

current was globally visited before

If the node is not in the current traversal's distance map, then it belongs to a previously processed traversal and no new cycle is formed.

Case 3:

current exists in distance

This means we revisited a node within the same traversal, so we found a cycle. 7. Compute the cycle length.

Suppose:

distance[current] = first_seen
current_step = step

Then:

cycle_length = step - first_seen
  1. Update longest_cycle if the newly found cycle is larger.
  2. Continue until all nodes have been processed.

Why it works

The algorithm works because every node has at most one outgoing edge, which guarantees a unique traversal path from each starting node.

The distance map identifies nodes visited during the current traversal only. Therefore, revisiting a node inside this map means we have closed a cycle. The difference in traversal steps gives the exact cycle length.

The global visited array guarantees efficiency by ensuring no node is processed more than once overall.

Python Solution

from typing import List

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

        for start in range(n):
            if visited[start]:
                continue

            current = start
            step = 0
            distance = {}

            while current != -1 and not visited[current]:
                visited[current] = True
                distance[current] = step

                step += 1
                current = edges[current]

            if current != -1 and current in distance:
                cycle_length = step - distance[current]
                longest_cycle = max(longest_cycle, cycle_length)

        return longest_cycle

The implementation begins by creating the visited array and initializing the result variable.

The outer loop iterates through all nodes. If a node has already been processed, we skip it immediately to avoid repeated work.

For each new traversal, we initialize:

  • current as the starting node
  • step to count traversal depth
  • distance to record the order nodes are visited in the current traversal

Inside the while loop, we continue traversing until:

  • We reach -1
  • We encounter a globally visited node

Each node is marked globally visited immediately, ensuring future traversals skip it.

The distance dictionary stores the step index when the node was first seen during the current traversal. If we later revisit a node inside this dictionary, we have found a cycle entirely within the current traversal path.

The cycle length is computed using:

current_step - first_seen_step

Finally, we update the maximum cycle length found so far.

Go Solution

func longestCycle(edges []int) int {
	n := len(edges)
	visited := make([]bool, n)
	longestCycle := -1

	for start := 0; start < n; start++ {
		if visited[start] {
			continue
		}

		current := start
		step := 0
		distance := make(map[int]int)

		for current != -1 && !visited[current] {
			visited[current] = true
			distance[current] = step

			step++
			current = edges[current]
		}

		if current != -1 {
			if firstSeen, exists := distance[current]; exists {
				cycleLength := step - firstSeen
				if cycleLength > longestCycle {
					longestCycle = cycleLength
				}
			}
		}
	}

	return longestCycle
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used instead of a Python dictionary for tracking traversal distances.

Go slices are naturally dynamic references, so the visited boolean slice efficiently tracks globally processed nodes.

Integer overflow is not a concern because the maximum cycle length is bounded by n, which is at most 100000.

Worked Examples

Example 1

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

Graph structure:

0 -> 3
1 -> 3
2 -> 4
3 -> 2
4 -> 3

Cycle:

2 -> 4 -> 3 -> 2

Traversal starting from node 0

Step Current Node Distance Map Next Node
0 0 {0: 0} 3
1 3 {0: 0, 3: 1} 2
2 2 {0: 0, 3: 1, 2: 2} 4
3 4 {0: 0, 3: 1, 2: 2, 4: 3} 3

Now 3 already exists in distance.

Cycle length:

step - distance[3]
= 4 - 1
= 3

So:

longest_cycle = 3

All nodes involved are now globally visited.

Remaining traversals are skipped.

Final answer:

3

Example 2

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

Graph structure:

0 -> 2
1 -> -1
2 -> 3
3 -> 1

Traversal from node 0

Step Current Node Distance Map Next Node
0 0 {0: 0} 2
1 2 {0: 0, 2: 1} 3
2 3 {0: 0, 2: 1, 3: 2} 1
3 1 {0: 0, 2: 1, 3: 2, 1: 3} -1

Traversal ends at -1.

No cycle exists.

Final answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is processed at most once
Space O(n) Visited array and traversal map together store at most n nodes

The critical optimization is the global visited array. Without it, nodes could be revisited repeatedly from different starting points. Since each node becomes globally visited exactly once, the total amount of traversal work across the entire algorithm is linear.

The distance dictionary used during each traversal also stores nodes only temporarily, and across all traversals its total size never exceeds n.

Test Cases

from typing import List

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

        for start in range(n):
            if visited[start]:
                continue

            current = start
            step = 0
            distance = {}

            while current != -1 and not visited[current]:
                visited[current] = True
                distance[current] = step

                step += 1
                current = edges[current]

            if current != -1 and current in distance:
                cycle_length = step - distance[current]
                longest_cycle = max(longest_cycle, cycle_length)

        return longest_cycle

solution = Solution()

assert solution.longestCycle([3, 3, 4, 2, 3]) == 3  # Example with cycle length 3
assert solution.longestCycle([2, -1, 3, 1]) == -1  # No cycles anywhere
assert solution.longestCycle([1, 2, 0]) == 3  # Entire graph is one cycle
assert solution.longestCycle([1, 2, 3, 4, 2]) == 3  # Long chain entering cycle
assert solution.longestCycle([-1, -1, -1]) == -1  # All nodes terminate immediately
assert solution.longestCycle([1, 0, 3, 2]) == 2  # Two separate cycles of equal size
assert solution.longestCycle([1, 2, 3, 1]) == 3  # Cycle not starting at traversal root
assert solution.longestCycle([4, 4, 4, 4, 5, 6, 3]) == 4  # Larger cycle with many incoming edges
assert solution.longestCycle([1, -1]) == -1  # Smallest valid graph without cycle
assert solution.longestCycle([2, 0, 1]) == 3  # Three-node cycle
Test Why
[3,3,4,2,3] Validates standard cycle detection
[2,-1,3,1] Validates graphs with no cycles
[1,2,0] Entire graph forms one cycle
[1,2,3,4,2] Tests chain leading into cycle
[-1,-1,-1] All nodes terminate immediately
[1,0,3,2] Multiple disconnected cycles
[1,2,3,1] Cycle begins after traversal starts
[4,4,4,4,5,6,3] Many incoming paths converge into cycle
[1,-1] Small boundary input
[2,0,1] Simple directed cycle

Edge Cases

One important edge case is a graph with no cycles at all. In this situation, every traversal eventually reaches -1. A buggy implementation might incorrectly treat revisiting globally visited nodes as cycles. This implementation avoids that by checking whether the repeated node exists inside the current traversal's distance map. Only nodes revisited during the same traversal count as cycles.

Another critical edge case is a long chain leading into a cycle. For example:

0 -> 1 -> 2 -> 3 -> 4 -> 2

Here, the cycle contains only nodes 2, 3, and 4. A naive implementation might incorrectly count the entire traversal length. This solution correctly computes:

current_step - distance[current]

which measures only the cycle portion.

A third important edge case involves multiple disconnected components. Some components may contain cycles while others do not. The algorithm handles this naturally because the outer loop starts traversals from every unvisited node. Each connected component is processed independently, and the maximum cycle length across all components is returned.

A final subtle edge case is encountering nodes already processed from earlier traversals. Without a global visited array, the algorithm would repeatedly traverse the same structures and become inefficient. By marking nodes globally visited immediately, the implementation guarantees each node is processed once, preserving linear complexity.