67. Topological Sort

Medium

Topics

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: graph = {0: [1, 2], 1: [3], 2: [3], 3: []}

Output: [0, 1, 2, 3]

Explanation: A valid topological order for the given graph. Node 0 comes before 1 and 2, 1 and 2 come before 3, and 3 has no outgoing edges.

Input: graph = {0: [1], 1: [2], 2: [0]}

Output: []

Explanation: The graph contains a cycle (0 -> 1 -> 2 -> 0), so a topological sort is not possible. An empty array is returned.

Input: graph = {0: [], 1: [], 2: [0, 1]}

Output: [2, 0, 1]

Explanation: A valid topological sort. Node 2 has dependencies on 0 and 1, so it comes first. 0 and 1 can be in either order after 2.

Input: graph = {0: [1], 2: [3], 1: [2], 3: []}

Output: [0, 1, 2, 3]

Explanation: The graph contains the following edges: 0->1, 1->2, 2->3, and also has the node 3. The correct toposort order is [0, 1, 2, 3]

Time Complexity

O(V+E)

Space Complexity

O(V)