Topological Sort Pattern

Overview

Linear ordering of vertices in a Directed Acyclic Graph (DAG) where for every edge (u, v), u comes before v. Used for dependency resolution and scheduling problems.

When to Use

• Task scheduling with dependencies
• Course prerequisites
• Build systems (compilation order)
• Detecting cycles in directed graph
• Finding valid ordering

Template Code

Kahn's Algorithm (BFS - In-degree)

public int[] topologicalSort(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];

    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    // Build graph and calculate in-degrees
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }

    // Add all nodes with in-degree 0 to queue
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    int[] result = new int[n];
    int index = 0;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        result[index++] = node;

        for (int neighbor : graph.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    // Check if valid ordering exists (no cycle)
    return index == n ? result : new int[0];
}

DFS Approach (Reverse Post-order)

public int[] topologicalSortDFS(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
    }

    Stack<Integer> stack = new Stack<>();
    int[] state = new int[n];  // 0=unvisited, 1=visiting, 2=visited

    for (int i = 0; i < n; i++) {
        if (state[i] == 0) {
            if (!dfs(graph, i, state, stack)) {
                return new int[0];  // Cycle detected
            }
        }
    }

    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = stack.pop();
    }
    return result;
}

private boolean dfs(List<List<Integer>> graph, int node,
                    int[] state, Stack<Integer> stack) {
    if (state[node] == 1) return false;  // Cycle detected
    if (state[node] == 2) return true;   // Already processed

    state[node] = 1;  // Visiting

    for (int neighbor : graph.get(node)) {
        if (!dfs(graph, neighbor, state, stack)) {
            return false;
        }
    }

    state[node] = 2;  // Visited
    stack.push(node);  // Add to result in reverse order
    return true;
}

Course Schedule (Can Finish)

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);  // pre[1] → pre[0]
        inDegree[pre[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    int completed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        completed++;

        for (int next : graph.get(course)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }

    return completed == numCourses;
}

Course Schedule II (Return Order)

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    int[] order = new int[numCourses];
    int index = 0;

    while (!queue.isEmpty()) {
        int course = queue.poll();
        order[index++] = course;

        for (int next : graph.get(course)) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }

    return index == numCourses ? order : new int[0];
}

Alien Dictionary

public String alienOrder(String[] words) {
    // Build adjacency list and in-degree
    Map<Character, Set<Character>> graph = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();

    // Initialize all characters
    for (String word : words) {
        for (char c : word.toCharArray()) {
            graph.putIfAbsent(c, new HashSet<>());
            inDegree.putIfAbsent(c, 0);
        }
    }

    // Build edges from adjacent word comparisons
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i], w2 = words[i + 1];
        int minLen = Math.min(w1.length(), w2.length());

        // Check for invalid case: prefix comes after
        if (w1.length() > w2.length() && w1.startsWith(w2)) {
            return "";
        }

        for (int j = 0; j < minLen; j++) {
            if (w1.charAt(j) != w2.charAt(j)) {
                char from = w1.charAt(j);
                char to = w2.charAt(j);

                if (!graph.get(from).contains(to)) {
                    graph.get(from).add(to);
                    inDegree.put(to, inDegree.get(to) + 1);
                }
                break;
            }
        }
    }

    // Topological sort using BFS
    Queue<Character> queue = new LinkedList<>();
    for (char c : inDegree.keySet()) {
        if (inDegree.get(c) == 0) {
            queue.offer(c);
        }
    }

    StringBuilder result = new StringBuilder();
    while (!queue.isEmpty()) {
        char c = queue.poll();
        result.append(c);

        for (char neighbor : graph.get(c)) {
            inDegree.put(neighbor, inDegree.get(neighbor) - 1);
            if (inDegree.get(neighbor) == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return result.length() == inDegree.size() ? result.toString() : "";
}

Parallel Courses (Minimum Semesters)

public int minimumSemesters(int n, int[][] relations) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n + 1];

    for (int i = 0; i <= n; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] rel : relations) {
        graph.get(rel[0]).add(rel[1]);
        inDegree[rel[1]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    int semesters = 0;
    int completed = 0;

    while (!queue.isEmpty()) {
        semesters++;
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            int course = queue.poll();
            completed++;

            for (int next : graph.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
    }

    return completed == n ? semesters : -1;
}

All Topological Orderings

public List<List<Integer>> allTopologicalSorts(int n, int[][] edges) {
    List<List<Integer>> result = new ArrayList<>();
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];

    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }

    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }

    boolean[] visited = new boolean[n];
    List<Integer> current = new ArrayList<>();

    backtrack(graph, inDegree, visited, current, result, n);
    return result;
}

private void backtrack(List<List<Integer>> graph, int[] inDegree,
                       boolean[] visited, List<Integer> current,
                       List<List<Integer>> result, int n) {
    if (current.size() == n) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!visited[i] && inDegree[i] == 0) {
            // Choose
            visited[i] = true;
            current.add(i);
            for (int neighbor : graph.get(i)) {
                inDegree[neighbor]--;
            }

            // Explore
            backtrack(graph, inDegree, visited, current, result, n);

            // Unchoose
            visited[i] = false;
            current.remove(current.size() - 1);
            for (int neighbor : graph.get(i)) {
                inDegree[neighbor]++;
            }
        }
    }
}

Time & Space Complexity

Problem	Time	Space
Topological sort	O(V + E)	O(V + E)
Course schedule	O(V + E)	O(V + E)
Alien dictionary	O(C)	O(1)
All orderings	O(V! × V)	O(V + E)

Common Interview Questions

1. Course Schedule - Can finish all courses?
2. Course Schedule II - Return valid order
3. Alien Dictionary - Derive character order
4. Parallel Courses - Min semesters to finish
5. Sequence Reconstruction - Unique topological order?
6. Minimum Height Trees - Find centroids (remove leaves)
7. Build Order - Package dependencies
8. Sort Items by Groups - Two-level topo sort
9. Longest Increasing Path in Matrix - DFS + memo or topo
10. Find All Possible Recipes - Multi-dependency resolution

Tips & Tricks

• Kahn's (BFS) is intuitive and easier to implement
• DFS gives reverse order (use stack or reverse at end)
• If result size < V, cycle exists
• Use PriorityQueue instead of Queue for lexicographically smallest order
• Track level for "minimum stages/semesters" problems
• For multiple valid orderings, use backtracking