Topological Sort Pattern: LeetCode Guide & Problems

Linear ordering of vertices in a DAG — essential for dependency problems.

✓ Pattern Solutions & Guides Practice Mode Enabled

5 Problem 0 Easy 4 Medium 1 Hard

Overview

Topological sort orders vertices so all edges point forward. It applies to any problem with dependencies: course scheduling, build systems, task ordering.

When to Use

Course Schedule (detect cycle)
Course Schedule II (ordering)
Alien dictionary
Minimum height trees
Parallel courses

Common Mistakes

Not detecting cycles before claiming a valid order exists
Using Kahn's algorithm vs DFS-based — both work, choose one
Bidirectional edges in a topological sort context

Complexity

Time

O(V + E)

Space

O(V)

// Kahn's Algorithm (BFS-based)
public int[] topoSort(int n, int[][] prerequisites) {
    int[] inDegree = new int[n];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

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

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

    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        order[idx++] = node;
        for (int nei : adj.get(node)) {
            if (--inDegree[nei] == 0) queue.offer(nei);
        }
    }
    return idx == n ? order : new int[]{}; // empty = cycle exists
}

Problems (5)

Hide completed

Problem	Difficulty	Companies	Freq	Solution	Link
Course Schedule #Graph #DFS #BFS	Medium	AmazonFacebook +2	High	Solution
Course Schedule II #Graph #DFS #BFS	Medium	FacebookAmazon +1	High	Solution
Parallel Courses ★ #Graph #Topological Sort #BFS	Medium	AmazonGoogle	Medium	Solution	★
Sequence Reconstruction ★ #Array #Graph #Topological Sort	Medium	GoogleSnapchat	Low	Solution	★
Alien Dictionary ★ #Array #String #Graph	Hard	FacebookAmazon +3	High	Solution	★

🧠

Mastering the Topological Sort Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Topological Sort pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Topological Sort, the target time complexity is typically O(V + E) while maintaining an auxiliary space complexity of O(V). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.