What is Topological Sort?
A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u → v), u appears before v. This represents a valid execution order for tasks with dependencies. Topological sort is only possible if the graph has no cycles (it is a DAG). If a cycle exists, no valid ordering exists. Two standard algorithms: Kahn’s (BFS-based, uses in-degree) and DFS post-order.
Kahn’s Algorithm (BFS-based)
Maintain the in-degree (number of incoming edges) for each node. Start with all nodes whose in-degree is 0 (no dependencies). Repeatedly: remove a zero-in-degree node from the queue, add to the result, decrement the in-degree of its neighbors, enqueue neighbors that now have in-degree 0. If the result contains all nodes: valid topological order. If fewer than all nodes: the graph has a cycle (the remaining nodes form a cycle with no zero-in-degree entry point).
from collections import deque
def topological_sort_kahn(graph, n):
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return order if len(order) == n else [] # empty = cycle detectedDFS Post-Order
DFS-based topological sort: run DFS on every unvisited node. When DFS finishes a node (all its descendants are processed), push it onto a stack. Reverse the stack to get the topological order. Cycle detection: track three states — UNVISITED, VISITING (currently in the DFS stack), VISITED (fully processed). If we encounter a VISITING node during DFS: a back edge exists — cycle detected.
def topological_sort_dfs(graph, n):
UNVISITED, VISITING, VISITED = 0, 1, 2
state = [UNVISITED] * n
result = []
has_cycle = [False]
def dfs(u):
if has_cycle[0]: return
state[u] = VISITING
for v in graph[u]:
if state[v] == VISITING:
has_cycle[0] = True; return
if state[v] == UNVISITED:
dfs(v)
state[u] = VISITED
result.append(u)
for i in range(n):
if state[i] == UNVISITED:
dfs(i)
return [] if has_cycle[0] else result[::-1]Course Schedule (LC 207, 210)
LC 207: can all courses be finished? = does the prerequisite graph have a cycle? Run Kahn’s: if the topological order contains all courses, no cycle. LC 210: return a valid course order. Return the topological order from Kahn’s. Both use the same algorithm — 207 just checks existence, 210 returns the actual order. Key: build the adjacency list from the prerequisites list: prerequisites[i] = [a, b] means b → a (b is a prerequisite of a — b must come before a). Edge direction: b → a means a depends on b.
Parallel Tasks with Dependencies (LC 1136, 1203)
LC 1136 (Parallel Courses): find the minimum number of semesters to complete all courses, where you can take multiple courses in parallel if their prerequisites are satisfied. Modified Kahn’s: process all zero-in-degree nodes in one semester (one BFS level). Count the number of BFS levels = minimum semesters. LC 1203 (Sort Items by Groups Respecting Dependencies): two-level topological sort. First sort items within each group; then sort groups. Build a group-level DAG and an item-level DAG. Run topological sort on both; combine results.
Alien Dictionary (LC 269)
Given a sorted list of words in an alien language, determine the character ordering. Build a DAG: for each adjacent pair of words, find the first differing character position — that pair gives an edge (earlier_char → later_char). Run topological sort on the character DAG. Edge case: if word A is a prefix of word B but appears after B in the list, the input is invalid (return “”.) O(C) time where C = total characters in all words.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide