Dashboard/Coding patterns/15. Topological Sort

CODING PATTERNS · LESSON 15 OF 28 · 38 MIN VIDEO · 12 PROBLEMS

Topological Sort

Module Progress (0 / 12 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (38 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Topological Sort — How the Pattern Works

Topological Sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u precedes vertex v. Kahn's algorithm maintains the invariant that indeg[v] tracks the exact count of unresolved prerequisites of v, dequeuing only vertices with indeg[v] == 0 whose dependencies have all been satisfied. Because each vertex enters and exits the ready queue at most once and each directed edge is relaxed once, it reduces O(V! * E) permutation testing and O(V(V + E)) repeated traversals to O(V + E) time for dependency ordering, cycle detection, and DAG dynamic programming.

WHEN TO USE THIS PATTERN
  • The input specifies pairwise precedence constraints (prerequisites, build dependencies, recipes and ingredients, or row/column ordering rules) and asks for a valid execution order or feasibility check.
  • A hidden partial or total ordering must be inferred from sorted sequential data (such as adjacent words in an alien dictionary) or decomposed across hierarchy levels (groups and intra-group items).
  • Tasks with dependencies can execute concurrently and the prompt asks for the minimum number of parallel rounds/semesters (BFS layers) or earliest completion time (critical-path DP).
  • A tree problem aggregates child states into parents or shrinks an unrooted tree inward by iteratively peeling leaf nodes (degree <= 1 or children == 0).
COMMON INTERVIEW PITFALLS
  • Reversing directed edge orientation when reading input pairs: [course, pre] means pre -> course (indeg[course] += 1), whereas [prev, next] means prev -> next (indeg[next] += 1).
  • Omitting the cycle check on completion: Kahn's loop exits cleanly when cycles trap remaining nodes at indeg > 0, so always verify len(order) == V (or taken == V) before returning.
  • Ignoring prefix violations or extracting multiple edges per word pair in Alien Dictionary: ["abc", "ab"] is invalid despite having no differing characters, and characters past the first mismatch carry no ordering rule.
  • Mutating the current frontier mid-layer during level-by-level or leaf-peeling passes: snapshot each round's frontier before removing edges, and check len(adj[v]) > 0 when peeling the final edge between two leaves.
Kahn's Topological Sort (Linear Order and Cycle Detection)Use to compute a valid dependency ordering of n nodes and detect directed cycles when len(order) < n.
def kahn_topo_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
    graph, indeg = [[] for _ in range(n)], [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    order = [u for u in range(n) if indeg[u] == 0]
    for u in order:
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                order.append(v)
    return order if len(order) == n else []
Layered Kahn's Peel (Minimum Parallel Rounds)Use when all currently ready tasks (indeg == 0) run simultaneously in discrete rounds or semesters.
def min_parallel_rounds(n: int, edges: list[tuple[int, int]]) -> int:
    graph, indeg = [[] for _ in range(n)], [0] * n
    for u, v in edges: graph[u].append(v); indeg[v] += 1
    layer, rounds, taken = [u for u in range(n) if indeg[u] == 0], 0, 0
    while layer:
        rounds, taken, nxt = rounds + 1, taken + len(layer), []
        for u in layer:
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0: nxt.append(v)
        layer = nxt
    return rounds if taken == n else -1
DAG Critical-Path Dynamic ProgrammingUse when nodes have individual durations/weights and each node starts as soon as its slowest prerequisite finishes.
def dag_critical_path(n: int, edges: list[tuple[int, int]], cost: list[int]) -> int:
    graph, indeg = [[] for _ in range(n)], [0] * n
    for u, v in edges:
        graph[u].append(v); indeg[v] += 1
    end, order = cost[:], [u for u in range(n) if indeg[u] == 0]
    for u in order:
        for v in graph[u]:
            end[v] = max(end[v], end[u] + cost[v])
            indeg[v] -= 1
            if indeg[v] == 0: order.append(v)
    return max(end, default=0)
🔒 PRO PROBLEMTarget: O(total letters) time

02. Alien Dictionary

Pattern Trigger: hidden order from sorted data → arrows + topo sort

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Kahn's queue runs empty, but two nodes were never taken. What does that tell you?