May 18, 2025

Topological Sort

Overview

A topological sort orders a directed graph so every edge u -> v places u before v. Such an order exists only when the graph is a directed acyclic graph (DAG).

Kahn’s algorithm tracks each node’s indegree, or number of incoming edges. Nodes with indegree zero have no remaining prerequisites, so they can be processed immediately. Processing a node removes its outgoing edges; any neighbor whose indegree becomes zero is added to the queue. If fewer than V nodes are processed, the graph contains a cycle.

The graph may be explicit, such as a course prerequisite adjacency list, or implicit, such as neighboring matrix cells. For an implicit graph, calculate outgoing neighbors when needed instead of building an adjacency list. Processing the queue one layer at a time also finds the longest path length in a DAG: each layer contains nodes whose longest prerequisite chain has the same length.

The runtime is O(V + E) and the auxiliary space is O(V + E) for an explicit adjacency list.

Templates

Build each directed edge u -> v: add v to u’s neighbors and increment v’s indegree.
Add every node with indegree zero to the queue.
Repeatedly remove a node, record it, and decrement the indegree of each outgoing neighbor.
Add a neighbor when its indegree reaches zero.
Return the order only if it contains all nodes; otherwise, a cycle exists.

import java.util.*;

class TopologicalSort {
	public List<Integer> sort(int n, int[][] edges) {
		List<List<Integer>> adjList = new ArrayList<>();
		int[] inDegrees = new int[n];
		for (int u = 0; u < n; u++) adjList.add(new ArrayList<>());
		for (int[] edge : edges) {
			int u = edge[0], v = edge[1];
			adjList.get(u).add(v);
			inDegrees[v]++;
		}

		Deque<Integer> dq = new ArrayDeque<>();
		for (int u = 0; u < n; u++) if (inDegrees[u] == 0) dq.addLast(u);
		List<Integer> res = new ArrayList<>();
		while (!dq.isEmpty()) {
			int u = dq.removeFirst();
			res.add(u);
			for (int v : adjList.get(u))
				if (--inDegrees[v] == 0) dq.addLast(v);
		}
		return res.size() == n ? res : List.of();
	}
}

from collections import deque

def topological_sort(n, edges):
    adj_list = [[] for _ in range(n)]
    in_degrees = [0] * n
    for u, v in edges:
        adj_list[u].append(v)
        in_degrees[v] += 1

    dq = deque(u for u in range(n) if in_degrees[u] == 0)
    res = []
    while dq:
        u = dq.popleft()
        res.append(u)
        for v in adj_list[u]:
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                dq.append(v)

    return res if len(res) == n else []

Problems

210. Course Schedule II

Return one valid course order, or an empty array if a cycle prevents completion. This is the constructive form of Kahn’s algorithm: write every removed zero-indegree course into the result.

import java.util.*;

class Solution {
	public int[] findOrder(int numCourses, int[][] prerequisites) {
		List<List<Integer>> adjList = new ArrayList<>();
		int[] inDegrees = new int[numCourses];
		List<Integer> res = new ArrayList<>();

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

		for (int[] edge : prerequisites) {
			int u = edge[0];
			int v = edge[1];
			adjList.get(v).add(u);
			inDegrees[u]++;
		}

		Deque<Integer> dq = new ArrayDeque<>();

		for (int idx = 0; idx < inDegrees.length; idx++) {
			int val = inDegrees[idx];
			if (val == 0) {
				dq.addLast(idx);
			}
		}

		while (!dq.isEmpty()) {
			int u = dq.removeFirst();
			res.add(u);
			for (int v : adjList.get(u)) {
				inDegrees[v]--;
				if (inDegrees[v] == 0) {
					dq.addLast(v);
				}
			}
		}

		if (res.size() != numCourses) {
			return new int[0];
		}

		int[] order = new int[numCourses];
		for (int i = 0; i < numCourses; i++) {
			order[i] = res.get(i);
		}
		return order;
	}
}

import collections
from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj_list = collections.defaultdict(list)
        in_degrees = [0] * numCourses
        res = []

        for u, v in prerequisites:
            adj_list[v].append(u)
            in_degrees[u] += 1

        dq = collections.deque()

        for idx, val in enumerate(in_degrees):
            if val == 0:
                dq.append(idx)

        while dq:
            u = dq.popleft()
            res.append(u)
            for v in adj_list[u]:
                in_degrees[v] -= 1
                if in_degrees[v] == 0:
                    dq.append(v)

        return res if len(res) == numCourses else []

329. Longest Increasing Path in a Matrix

Direct every edge from a smaller cell to a larger neighbor. Values strictly increase, so the graph is acyclic. Kahn’s algorithm processes local minima first; each BFS layer advances one step along an increasing path, making the number of layers the longest length.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int longestIncreasingPath(int[][] matrix) {
		int R = matrix.length;
		int C = matrix[0].length;
		int[][] inDegree = new int[R][C];
		int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				for (int[] direction : directions) {
					int dr = direction[0];
					int dc = direction[1];
					int nr = r + dr;
					int nc = c + dc;
					if (nr >= 0 && nr < R && nc >= 0 && nc < C && matrix[nr][nc] < matrix[r][c]) {
						inDegree[r][c]++;
					}
				}
			}
		}

		Deque<int[]> dq = new ArrayDeque<>();
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (inDegree[r][c] == 0) {
					dq.addLast(new int[] {r, c});
				}
			}
		}

		int step = 0;
		while (!dq.isEmpty()) {
			int size = dq.size();
			for (int i = 0; i < size; i++) {
				int[] curr = dq.removeFirst();
				int currR = curr[0];
				int currC = curr[1];
				for (int[] direction : directions) {
					int dr = direction[0];
					int dc = direction[1];
					int nextR = currR + dr;
					int nextC = currC + dc;
					if (nextR >= 0 && nextR < R && nextC >= 0 && nextC < C &&
						matrix[nextR][nextC] > matrix[currR][currC]) {
						inDegree[nextR][nextC]--;
						if (inDegree[nextR][nextC] == 0) {
							dq.addLast(new int[] {nextR, nextC});
						}
					}
				}
			}
			step++;
		}

		return step;
	}
}

from collections import deque
from typing import List

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        R, C = len(matrix), len(matrix[0])

        # Same as Course Schedule topological sourt
        inDegree = [[0]*C for _ in range(R)]
        directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

        for r in range(R):
            for c in range(C):
                for dr, dc in directions:
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < R and 0 <= nc < C and matrix[nr][nc] < matrix[r][c]:
                        inDegree[r][c] += 1

        # No need to have a set to track visited nodes
        # Actually we CANNOT do normal BFS with seen set!
        # Start from local minimums with no inDegree
        # You cannot go back, edge is directional.
        dq = deque()
        for r in range(R):
            for c in range(C):
                if inDegree[r][c] == 0:
                    dq.append((r, c))

        step = 0
        while dq:
            for _ in range(len(dq)):
                curr_r, curr_c = dq.popleft()
                for dr, dc in directions:
                    next_r, next_c = curr_r + dr, curr_c + dc
                    # A cell should enter layer L only when the longest increasing path ending at that cell has length L.
                    if 0 <= next_r < R and 0 <= next_c < C and matrix[next_r][next_c] > matrix[curr_r][curr_c]:
                        inDegree[next_r][next_c] -= 1
                        if inDegree[next_r][next_c] == 0:
                            dq.append((next_r, next_c))
            step += 1

        return step