Find Eventual Safe States

MediumGraphstopological sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A directed graph with n nodes is given as graph, where graph[i] lists the nodes that i has edges to. A node with no outgoing edges is a **terminal** node. A node is **safe** if every possible walk starting from it eventually reaches a terminal node — that is, no walk from it can go on forever by entering a cycle. Terminal nodes are safe. Return all safe nodes sorted in **ascending** order. Self-loops may appear and make a node unsafe.

Examples

Input: graph = [[1],[2],[0,3],[],[3,5],[]]
Output: [3,4,5]
Nodes 0, 1 and 2 sit on the cycle 0 -> 1 -> 2 -> 0. Nodes 3 and 5 are terminal, and node 4 only leads to them.
Input: graph = [[0],[0,2],[]]
Output: [2]
Node 0 has a self-loop, and node 1 can walk into it; only node 2 is safe.

Constraints

  • 1 <= n <= 10^4
  • 0 <= graph[i].length <= n
  • graph[i] is sorted with no duplicates
  • The total number of edges is at most 4 * 10^4

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More topological sort problems