Lesson 43Advanced59 minAssessment-backed

Topological Sort

Order dependent work in DAGs such as builds, jobs, course prerequisites, migrations, and workflow steps.

What you will be able to do

Explain topological order as a valid dependency-respecting order.

Use Kahn's algorithm with indegrees and a queue.

Detect cycles when not all nodes can be processed.

Model build pipelines, course prerequisites, and workflow dependencies.

Compare topological sort with DFS cycle detection.

Topological sort answers: in what order can we do work when some tasks must happen before others? It only exists for directed acyclic graphs.

Dependency Order

If edge A -> B means A must happen before B, then A must appear earlier in the output. If a cycle exists, no valid order exists.

DAG topological order — A topological order respects every directed dependency.

Scenario: Build Pipeline

A CI system must build shared libraries before services, run migrations before deployments, and block releases when dependencies cycle. Kahn's algorithm makes this operational: start with tasks that have no prerequisites.

Signal	Meaning	Action
Indegree 0	No remaining prerequisites	Queue it.
Process node	Task can run	Decrease dependent indegrees.
New indegree 0	Dependency now satisfied	Queue it.
Processed < total	Cycle exists	Fail with dependency error.

Kahn topological sort queue — Kahn's algorithm repeatedly removes nodes with no remaining prerequisites.

Same Pattern in Java, Python, and JavaScript

Course schedule ordering is the canonical topological-sort problem.

import java.util.*;

class CourseOrder {
    static int[] order(int n, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] edge : prerequisites) { graph.get(edge[1]).add(edge[0]); indegree[edge[0]]++; }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
        int[] out = new int[n]; int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll(); out[index++] = node;
            for (int next : graph.get(node)) if (--indegree[next] == 0) queue.offer(next);
        }
        return index == n ? out : new int[0];
    }
}

Assessment trap

Topological sort is for directed acyclic graphs. If dependencies cycle, the right result is a failure signal, not a partial order.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return one valid course order or an empty list if impossible.
Return whether all courses can be finished.
Given prerequisite relations, return the minimum semesters needed if any number of available courses can be taken each semester.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Build pipeline	Run services in arbitrary order.	Topologically order dependency DAG.	Cycle should block the release.
Migration planner	Trust written checklist order.	Build graph of prerequisites and process indegree-zero tasks.	Include isolated migrations.
Course prerequisite UI	Show partial order even with cycles.	Detect cycle and surface blocking prerequisites.	A partial order can mislead users.

Solved modelInterview Question Solutions

Question 1: Course Schedule II

Return one valid course order or an empty list if impossible. Use Kahn's algorithm. Nodes with indegree zero are currently unblocked; if not all nodes are emitted, a cycle exists.

import java.util.*;

class CourseOrder {
    static int[] order(int n, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] edge : prerequisites) { graph.get(edge[1]).add(edge[0]); indegree[edge[0]]++; }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
        int[] out = new int[n]; int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll(); out[index++] = node;
            for (int next : graph.get(node)) if (--indegree[next] == 0) queue.offer(next);
        }
        return index == n ? out : new int[0];
    }
}

Question 2: Course Schedule

Return whether all courses can be finished. The same indegree process solves the decision version. Finishing all nodes means every dependency cycle was absent.

import java.util.*;
class CourseSchedule { static boolean canFinish(int n, int[][] pre) { List<List<Integer>> g = new ArrayList<>(); int[] indeg = new int[n]; for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] p : pre) { g.get(p[1]).add(p[0]); indeg[p[0]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i); int seen = 0; while (!q.isEmpty()) { int node = q.poll(); seen++; for (int next : g.get(node)) if (--indeg[next] == 0) q.offer(next); } return seen == n; } }

Question 3: Minimum Semesters

Given prerequisite relations, return the minimum semesters needed if any number of available courses can be taken each semester. Run topological sort by layers. Each queue layer is one semester; a cycle prevents all courses from being scheduled.

import java.util.*;
class Semesters { static int minimum(int n, int[][] relations) { List<List<Integer>> g = new ArrayList<>(); int[] indeg = new int[n + 1]; for (int i = 0; i <= n; i++) g.add(new ArrayList<>()); for (int[] r : relations) { g.get(r[0]).add(r[1]); indeg[r[1]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i); int done = 0, semesters = 0; while (!q.isEmpty()) { for (int size = q.size(); size > 0; size--) { int node = q.poll(); done++; for (int next : g.get(node)) if (--indeg[next] == 0) q.offer(next); } semesters++; } return done == n ? semesters : -1; } }

Solved modelWorked Interview Answer

Return a valid course order or empty list if prerequisites contain a cycle. Kahn's algorithm repeatedly processes nodes with indegree zero. If not every node is processed, a cycle prevents a valid order.

import java.util.*;

class CourseOrder {
    static int[] order(int n, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] edge : prerequisites) { graph.get(edge[1]).add(edge[0]); indegree[edge[0]]++; }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);
        int[] out = new int[n]; int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll(); out[index++] = node;
            for (int next : graph.get(node)) if (--indegree[next] == 0) queue.offer(next);
        }
        return index == n ? out : new int[0];
    }
}

Hands-on drillTry It Yourself

Practice task

Draw dependencies A -> C, B -> C, C -> D. Compute indegrees, queue states, and final order.

Failure patternsCommon Mistakes to Avoid

Using topological sort on undirected graphs.
Forgetting isolated nodes.
Returning partial order when cycle exists.
Reversing edge direction.
Not defining what edge direction means.

Execution guardrailQuick-Start Checklist

Define edge meaning.
Build adjacency and indegree.
Queue indegree-zero nodes.
Process and decrement dependents.
Verify processed count.
Return cycle failure if incomplete.

Recall drillKnowledge Check

Question	Strong answer
When does topological order exist?	Only in a DAG.
What does indegree mean?	Number of unmet prerequisites.
How does Kahn detect cycles?	Processed count is less than total nodes.

VocabularyKey Terms

Term	Meaning
DAG	Directed acyclic graph.
Indegree	Incoming edge count.
Prerequisite	Dependency that must come first.
Kahn's algorithm	Queue-based topological sort.

Next practiceFurther Reading

Practice course schedule, alien dictionary, and parallel build planning.
Review DFS cycle detection.
Compare topological order uniqueness conditions.

Intervals and Scheduling

Union Find