Topological Sort Pattern in Java - Interview Preparation Guide

Topological sort is the graph pattern for turning dependency constraints in a DAG into a valid execution or build order. Strong candidates explain why the graph must be acyclic, what indegree or finish order represents, and how cycle detection is part of the algorithm instead of an afterthought.

Pattern Summary Table

Problem Statement

Given directed dependency edges, produce a valid ordering if one exists, or detect that a cycle makes the ordering impossible.

Pattern Recognition Signals

• Keywords in the problem: prerequisite, build order, dependency graph, DAG, cycle detection.
• Structural signal: every valid next step must currently have no unresolved incoming dependency.
• Complexity signal: the optimized version avoids repeated rescans, recomputation, or state explosion that brute force would suffer.

Java Template

public List<Integer> topoSort(int n, int[][] edges) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);

    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : g.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return order;
}

Dry Run (Kahn’s Algorithm)

n=4, edges: 0->1, 0->2, 1->3, 2->3

Initial indegree:

• 0:0, 1:1, 2:1, 3:2

Queue starts with [0].

1. pop 0, order [0], indegree of 1,2 becomes 0 -> enqueue 1,2
2. pop 1, order [0,1], indegree of 3 becomes 1
3. pop 2, order [0,1,2], indegree of 3 becomes 0 -> enqueue 3
4. pop 3, order [0,1,2,3]

All nodes processed => DAG and valid topological ordering.

Cycle Detection Rule

Kahn’s method detects cycle by count:

• if order.size() < n, graph has at least one cycle
• if equal, ordering exists

Always include this check in dependency-resolution problems.

DFS Topological Sort (Alternative)

DFS post-order + reverse gives topological order (for DAG):

1. run DFS from each unvisited node
2. push node after exploring neighbors
3. reverse finish order

For cycle detection in DFS, track recursion stack (visiting state).

Problem 1: Course Schedule II

Problem description: Given n courses and prerequisite pairs, return one valid order to finish all courses or an empty array if a cycle exists.

What we are solving actually: We are not just traversing a graph. We must repeatedly find courses whose remaining prerequisites are zero and detect when a cycle prevents any further progress.

What we are doing actually:

1. Build adjacency lists and indegree counts.
2. Push every zero-indegree course into a queue.
3. Pop ready courses, append them to the answer, and decrement dependent indegrees.
4. If we process fewer than n courses, a cycle blocked the ordering.

public int[] findOrder(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) {
        int course = edge[0], prereq = edge[1];
        graph.get(prereq).add(course);
        indegree[course]++; // This course is blocked until one more prerequisite is removed.
    }

    ArrayDeque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.offer(i); // Ready-to-take courses enter the queue immediately.
    }

    int[] order = new int[n];
    int idx = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[idx++] = u; // Fix the next course in the valid ordering.

        for (int v : graph.get(u)) {
            indegree[v]--; // One prerequisite for v has now been satisfied.
            if (indegree[v] == 0) q.offer(v); // v becomes available exactly now.
        }
    }
    return idx == n ? order : new int[0]; // Fewer than n processed courses means a cycle exists.
}

Debug steps:

• print the initial indegree array and queue before the BFS starts
• after each pop, log the updated indegree values of neighbors
• verify the invariant that only zero-indegree nodes are ever added to the queue

Problem-Fit Checklist

• Identify whether input size or query count requires preprocessing or specialized data structures.
• Confirm problem constraints (sorted input, non-negative weights, DAG-only, immutable array, etc.).
• Validate that the pattern gives asymptotic improvement over brute-force under worst-case input.
• Define explicit success criteria: value only, index recovery, count, path reconstruction, or ordering.

Invariant and Reasoning

• Write one invariant that must stay true after every transition (loop step, recursion return, or update).
• Ensure each step makes measurable progress toward termination.
• Guard boundary states explicitly (empty input, singleton, duplicates, overflow, disconnected graph).
• Add a quick correctness check using a tiny hand-worked example before coding full solution.

Complexity and Design Notes

• Compute time complexity for both preprocessing and per-query/per-update operations.
• Track memory overhead and object allocations, not only Big-O notation.
• Prefer primitives and tight loops in hot paths to reduce GC pressure in Java.
• If multiple variants exist, choose the one with the simplest correctness proof first.

Production Perspective

• Convert algorithmic states into explicit metrics (queue size, active nodes, cache hit ratio, relaxation count).
• Add guardrails for pathological inputs to avoid latency spikes.
• Keep implementation deterministic where possible to simplify debugging and incident analysis.
• Separate pure algorithm logic from I/O and parsing so the core stays testable.

Implementation Workflow

1. Implement the minimal correct template with clear invariants.
2. Add edge-case tests before optimizing.
3. Measure complexity-sensitive operations on realistic input sizes.
4. Refactor for readability only after behavior is locked by tests.

Common Mistakes

1. Choosing the pattern without proving problem fit.
2. Ignoring edge cases (empty input, duplicates, overflow, disconnected state).
3. Mixing multiple strategies without clear invariants.
4. No complexity analysis against worst-case input.

Practice Set (Recommended Order)

1. Course Schedule (LC 207)
   LeetCode
2. Course Schedule II (LC 210)
   LeetCode
3. Alien Dictionary (LC 269)
   LeetCode

Key Takeaways

• This pattern is most effective when transitions are explicit and invariants are enforced at every step.
• Strong preconditions and boundary handling make these implementations production-safe.
• Reuse this template and adapt it per problem constraints.