Algorithm1 Practice2 Interview

Topological Sort

GuideCode Labs

Order a directed acyclic graph so every dependency appears before its dependents. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Topological Sort when the prompt's constraints and required operations match this shape: Order a directed acyclic graph so every dependency appears before its dependents.

On this page · Order Every Edge Forward

Checking your account…

Order Every Edge Forward

A topological order lists every vertex of a directed acyclic graph so each edge source appears before its target. It is a precedence contract, not merely a traversal order.

Choose DFS Postorder or Indegrees

DFS appends a node after all dependencies and reverses postorder. Kahn’s algorithm repeatedly removes zero-indegree nodes. Both take O(V + E), but expose different cycle evidence and ordering controls.

Check a Candidate Topological Order

Reference

def is_topological_order(node_count,edges,order):
    if len(order)!=node_count or len(set(order))!=node_count:return False
    position={node:index for index,node in enumerate(order)}
    return all(source in position and target in position and position[source]<position[target] for source,target in edges)

Practice

Implement is_topological_order(node_count,edges,order). Return whether order contains every node once and places each directed edge forward.

def is_topological_order(node_count,edges,order):
    pass

Public tests

Require every edge to point forward

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Detect When No Order Exists

A directed cycle makes every cycle node depend on another cycle node. DFS detects an edge to the active path; Kahn detects that fewer than V nodes were processed.

Build a Deterministic Topological Order

Reference

import heapq

def topological_order(node_count,edges):
    adjacency=[[] for _ in range(node_count)];indegree=[0]*node_count
    for source,target in edges:adjacency[source].append(target);indegree[target]+=1
    ready=[node for node in range(node_count) if indegree[node]==0];heapq.heapify(ready);order=[]
    while ready:
        node=heapq.heappop(ready);order.append(node)
        for neighbor in adjacency[node]:
            indegree[neighbor]-=1
            if indegree[neighbor]==0:heapq.heappush(ready,neighbor)
    return order if len(order)==node_count else []

Practice

Implement topological_order(node_count,edges). Return the lexicographically smallest valid order, or [] for a cycle.

def topological_order(node_count,edges):
    pass

Public tests

Return deterministic DAG order or no order

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle Multiple Valid Orders

A DAG may have many valid orders. Use a heap when the contract requests lexicographically smallest output; otherwise any deterministic queue or traversal order is acceptable.

Explain It in an Interview

Say: “A valid order places every directed edge forward. I remove currently dependency-free nodes and decrement exactly their outgoing edges; processing fewer than V nodes proves a cycle.” Mention isolated nodes and duplicate-edge policy.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Topological Sort proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Topological Sort complete workflow	`O(V log V + E)`	`O(V log V + E)`	Dependency graphs expose currently available work as the nodes with zero remaining incoming edges. A node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once.

Space

O(V + E) for the focused Maintain an Indegree Frontier implementation.

Assumptions

Zero-indegree nodes form the available layer, and removing them updates each outgoing dependency exactly once. If every node is emitted the layers respect all edges; otherwise the remaining positive indegrees certify a directed cycle.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Topological Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
Each stored indegree equals the number of unmet incoming dependencies.
The queue contains exactly discovered vertices with zero unmet dependencies.
Dependency graphs expose currently available work as the nodes with zero remaining incoming edges. Preserve this claim after every transition.
A node enters a frontier exactly when all of its predecessors have been removed, and each edge decrements indegree once. Preserve this claim after every transition.

When To Use Or Avoid Topological Sort

Use It When

Use Topological Sort when this precondition is stated or can be proved: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.
Use it when this maintained state removes repeated work: Each stored indegree equals the number of unmet incoming dependencies.

Choose Another Tool When

Avoid Topological Sort when this precondition is absent: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Dependencies form a directed graph, and a complete ordering exists only when the graph is acyclic.

Avoid

def kahn_frontier_layers(node_count, edges):
    pass

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Maintain an Indegree Frontier(opens in a new tab)

Breaking the state transition

Returns partial layers without verifying that every node was processed, so directed cycles are accepted.

Prevent it: Preserve this proof obligation: Only zero-indegree vertices are emitted, so every prerequisite precedes each dependent; a short result reveals a cycle.

Avoid

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after); indegree[after] += 1
    frontier = [i for i, degree in enumerate(indegree) if degree == 0]
    layers = []
    while frontier:
        layers.append(sorted(frontier)); next_frontier = []
        for node in frontier:
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: next_frontier.append(neighbor)
        frontier = next_frontier
    return layers

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Maintain an Indegree Frontier(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(V log V + E).

Avoid

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after); indegree[after] += 1
    frontier = [i for i, degree in enumerate(indegree) if degree == 0]
    layers = []
    while frontier:
        layers.append(sorted(frontier)); next_frontier = []
        for node in frontier:
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0: next_frontier.append(neighbor)
        frontier = next_frontier
    return layers

Use instead

def kahn_frontier_layers(node_count, edges):
    graph = [[] for _ in range(node_count)]
    indegree = [0] * node_count
    for before, after in edges:
        graph[before].append(after)
        indegree[after] += 1
    frontier = [node for node, degree in enumerate(indegree) if degree == 0]
    layers = []
    processed = 0
    while frontier:
        frontier.sort()
        layers.append(frontier)
        next_frontier = []
        for node in frontier:
            processed += 1
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_frontier.append(neighbor)
        frontier = next_frontier
    return layers if processed == node_count else []

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12
Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…