Is there a loop in a one-way graph?
A directed graph has n vertices numbered 0 to n - 1. Each edges[i] = [u, v] is a one-way edge from u to v. The same edge may be listed twice, and an edge from a vertex to itself is allowed.
Return true if you can start at some vertex, follow edges in their direction, and come back to where you started. Return false otherwise.
- Input
n = 4
edges = [[0,1],[1,2],[2,0],[2,3]]- Output
true
0 to 1 to 2 and back to 0.
- Input
n = 3
edges = [[0,1],[0,2],[2,1]]- Output
false
Vertex 1 is reached two ways, but no path leads back to where it began.
- Input
n = 2
edges = [[1,1]]- Output
true
An edge from 1 to itself is a loop of length one.
Limits
1 <= n <= 50000 <= edges.length <= 200000 <= u, v < n
Hints
Hint 1
Count each vertex's incoming edges. Repeatedly take a vertex with none left and remove its outgoing edges.
Hint 2
If every vertex gets taken, there is no loop. Vertices that are never taken sit on a loop or behind one.
Where this was reported
- Amazon, SDE-1 interview, 2026 (Medium)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
