Skip to main content

25. Longest Cycle in a Graph

hardAsked at Palantir

Given a directed graph where each node has at most one outgoing edge, return the length of the longest cycle. Palantir asks this because their ontology validator must detect cycles in foreign-key constraints — and when each entity points to exactly one parent, the cycle search shape is precisely this problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2026-Q1)— Palantir FDE on-site — graded on iterative implementation, not just recursive.
  • Blind (2025-10)— Tagged as a Palantir 'foreign-key validator' framing.

Problem

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.

Constraints

  • n == edges.length
  • 2 <= n <= 10^5
  • -1 <= edges[i] < n
  • edges[i] != i

Examples

Example 1

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

Explanation: Cycle 2 -> 4 -> 3 -> 2, length 3.

Example 2

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

Explanation: No cycle.

Approaches

1. DFS with recursion + per-node timestamps

Color nodes white/gray/black. For each white node, DFS along its outgoing chain recording arrival times. If you hit a gray node, the chain length minus its arrival time = cycle length.

Time
O(n)
Space
O(n) recursion + timestamps
function longestCycle(edges) {
  const n = edges.length;
  const color = new Array(n).fill(0); // 0 white, 1 gray, 2 black
  const time = new Array(n).fill(0);
  let t = 0;
  let best = -1;
  function dfs(u, startT) {
    while (u !== -1 && color[u] === 0) {
      color[u] = 1;
      time[u] = t++;
      u = edges[u];
    }
    if (u !== -1 && color[u] === 1) {
      best = Math.max(best, t - time[u]);
    }
    // Walk again to mark black — done iteratively for simplicity here
  }
  for (let i = 0; i < n; i++) if (color[i] === 0) dfs(i, t);
  return best;
}

Tradeoff: Recursive — but we already converted to iterative inside dfs because each node has one outgoing edge. Still uses O(n) timestamp memory. Cleaner shapes below.

2. Iterative walk with per-walk start time

For each unvisited node, walk forward with a local arrival-time map. If we hit a node WE visited in this walk, that's a cycle of length (now - arrivalTime). If we hit a node from a PRIOR walk, no new cycle — just mark our walk visited.

Time
O(n)
Space
O(n)
function longestCycle(edges) {
  const n = edges.length;
  const visited = new Array(n).fill(false);
  let best = -1;
  for (let i = 0; i < n; i++) {
    if (visited[i]) continue;
    const arrival = new Map();
    let u = i;
    let step = 0;
    while (u !== -1 && !visited[u]) {
      arrival.set(u, step++);
      visited[u] = true;
      u = edges[u];
    }
    if (u !== -1 && arrival.has(u)) {
      best = Math.max(best, step - arrival.get(u));
    }
  }
  return best;
}

Tradeoff: Linear time, no recursion — survives n=10^5. Each node is touched at most twice (once during its walk, once as a destination of someone else's walk). The arrival map resets per walk, so total work is O(n).

Palantir-specific tips

Palantir wants the iterative version specifically — recursive DFS on 10^5 nodes WILL stack overflow in JavaScript. State the amortization explicitly: each node is visited at most twice across all walks, so the total work is O(n). Bonus signal: connect to the foreign-key validator framing — when every entity has at most one parent (a forest of arrows), this is the exact cycle check their ontology engine runs at write time to reject inconsistent updates. Mention that for general graphs (multiple outgoing edges) you'd need Tarjan's SCC algorithm.

Common mistakes

  • Using a single global visited set without per-walk arrival times — you can't distinguish 'visited in this chain' from 'visited in a previous chain'.
  • Resetting visited between walks — quadratic complexity.
  • Confusing the cycle length (number of nodes in the cycle) with the path length (steps to reach the cycle).

Follow-up questions

An interviewer at Palantir may pivot to one of these next:

  • Same problem but each node can have multiple outgoing edges — use Tarjan's SCC.
  • Find ALL cycles, not just the longest.
  • Shortest cycle containing a given node — BFS from that node.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this linear despite the outer for loop?

Because each node is visited at most twice across the entire algorithm: once as a 'walk source' (or skipped because visited), and once as a destination on someone else's walk. The total work is bounded by 2n.

Why does the arrival map have to be local to each walk?

Because a cycle is detected only when we revisit a node IN THE CURRENT WALK. Reusing a global map would let us misidentify a node from a previous walk as a cycle return.

Practice these live with InterviewChamp.AI

Drill Longest Cycle in a Graph and other Palantir interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →