Command Palette

Search for a command to run...

Hectal
Problem 23.6 · Cycle DetectionHard

Longest Cycle in a Graph

PatternGraph DFS and Flood FillFast and Slow Pointers

What it teaches: Functional graphs: walk with timestamps to measure each cycle once.

Practise it on judges as “Longest Cycle in a Graph”.

The problem

Each node i has at most one outgoing edge, to edges[i] (−1 for none). Return the length of the longest cycle, or −1 if there is none.

Example 1

Input: edges = [3,3,4,2,3]
Output: 3

2 → 4 → 3 → 2.

Constraints

  • 2 ≤ n ≤ 10⁵

Pattern clues in the wording

  • → At most one outgoing edge per node

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int longestCycle(int[] edges) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
edges = [3,3,4,2,3]
3
2
edges = [2,-1,3,1]
-1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Timestamped walks · O(n)
1

Timestamped walks

Time O(n) Space O(n)

Global clock. For each unvisited start, record startTime and walk, stamping nodes. If the walk stops at a node with stamp ≥ startTime, update the best with clock − stamp.

Approach 1
class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length, time = 1, best = -1;
        int[] when = new int[n];
        for (int i = 0; i < n; i++) {
            if (when[i] != 0) continue;
            int start = time, u = i;
            while (u != -1 && when[u] == 0) { when[u] = time++; u = edges[u]; }
            if (u != -1 && when[u] >= start) best = Math.max(best, time - when[u]);
        }
        return best;
    }
}

Verdict: Every node is stamped once.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No cycles
  • Self-loop (length 1)
  • Walk joining a cycle found earlier

Mistakes people make

  • Counting a cycle again when a later walk runs into it (its stamps are older than the walk's start).

Interview

Follow-up questions

How is this related to Linked List Cycle?