Longest Cycle in a Graph

Hard
464.

Longest Cycle in a Graph

Longest Cycle in a Graph is a hard coding problem on depth-first search, graph and topological sort, asked in Amazon and Google interviews.

You are given a directed graph of n nodes where each node has at most one outgoing edge: edges[i] is the node that i points to, or -1 if it points nowhere.

Return the length of the longest cycle, or -1 if the graph has no cycle.

Example 1

Input
edges = [3,3,4,2,3]
Output
3
Explanation
The cycle 2 → 4 → 3 → 2 has length 3.

Example 2

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

Example 3

Input
edges = [1,0]
Output
2

Constraints

  • 1 <= edges.length <= 40
  • -1 <= edges[i] < edges.length
  • edges[i] != i
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} edges
 * @return {number}
 */
var longestCycle = function(edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Cycle in a Graph — Solution in Python, Java & C++

Longest Cycle in a Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Longest Cycle in a Graph is a hard coding problem on depth-first search, graph and topological sort, asked in Amazon and Google interviews.

Problem statement

You are given a directed graph of n nodes where each node has at most one outgoing edge: edges[i] is the node that i points to, or -1 if it points nowhere.

Return the length of the longest cycle, or -1 if the graph has no cycle.

Example 1

Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The cycle 2 → 4 → 3 → 2 has length 3.

Example 2

Input: edges = [2,-1,3,1]
Output: -1

Example 3

Input: edges = [1,0]
Output: 2

Constraints

  • 1 <= edges.length <= 40
  • -1 <= edges[i] < edges.length
  • edges[i] != i

Hints for Longest Cycle in a Graph

  1. Hint 1

    With one outgoing edge per node, following the arrows from any start eventually repeats a node.

  2. Hint 2

    Stamp each node with a global visit time as you walk, and stop when you reach something already stamped.

  3. Hint 3

    If that node was stamped during the current walk, the cycle length is the difference between the current clock and its stamp.

How to solve Longest Cycle in a Graph

Each node has one outgoing edge, so following arrows from any unvisited start eventually hits a visited node. Stamp nodes with a global clock; if the hit node was stamped during the current walk, the cycle length is clock - stamp.

Approach

  1. For each unstamped i, record walkStart = clock and walk, stamping each node with clock++.
  2. When the walk reaches a stamped node with stamp ≥ walkStart, update best = clock - stamp.

Why it works

A functional graph's walk is a ρ shape; a node revisited within the same walk closes the cycle, and the stamps count exactly the nodes on it. Nodes stamped by earlier walks are already resolved.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Comparing against walkStart is what distinguishes a cycle from merging into an earlier walk's path.

Reference solution

Python

def longestCycle(edges) -> int:
    n = len(edges)
    visited_at = [-1] * n
    best = -1
    clock = 0
    for i in range(n):
        if visited_at[i] != -1:
            continue
        walk_start = clock
        node = i
        while node != -1 and visited_at[node] == -1:
            visited_at[node] = clock
            clock += 1
            node = edges[node]
        if node != -1 and visited_at[node] >= walk_start:
            best = max(best, clock - visited_at[node])
    return best

Java

public static int longestCycle(int[] edges) {
    int n = edges.length;
    int[] visitedAt = new int[n];
    Arrays.fill(visitedAt, -1);
    int best = -1, clock = 0;
    for (int i = 0; i < n; i++) {
        if (visitedAt[i] != -1) continue;
        int walkStart = clock;
        int node = i;
        while (node != -1 && visitedAt[node] == -1) {
            visitedAt[node] = clock++;
            node = edges[node];
        }
        if (node != -1 && visitedAt[node] >= walkStart) {
            best = Math.max(best, clock - visitedAt[node]);
        }
    }
    return best;
}

C++

int longestCycle(vector<int>& edges) {
    int n = (int) edges.size();
    vector<int> visitedAt(n, -1);
    int best = -1, clock = 0;
    for (int i = 0; i < n; i++) {
        if (visitedAt[i] != -1) continue;
        int walkStart = clock;
        int node = i;
        while (node != -1 && visitedAt[node] == -1) {
            visitedAt[node] = clock++;
            node = edges[node];
        }
        if (node != -1 && visitedAt[node] >= walkStart) {
            best = max(best, clock - visitedAt[node]);
        }
    }
    return best;
}

JavaScript

var longestCycle = function(edges) {
    const n = edges.length;
    const visitedAt = [];
    for (let i = 0; i < n; i++) visitedAt.push(-1);
    let best = -1;
    let clock = 0;
    for (let i = 0; i < n; i++) {
        if (visitedAt[i] !== -1) continue;
        const walkStart = clock;
        let node = i;
        while (node !== -1 && visitedAt[node] === -1) {
            visitedAt[node] = clock++;
            node = edges[node];
        }
        if (node !== -1 && visitedAt[node] >= walkStart) {
            const length = clock - visitedAt[node];
            if (length > best) best = length;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Graph Data Structure