Coding Patterns
Topological Sort
Code Templates

Code Templates

The most reliable way to implement Topological Sort in an interview is Kahn’s Algorithm (BFS). It is easier to explain, naturally handles cycle detection, and avoids potential stack overflow issues from deep recursion in DFS.

For theoretical background on how this works, see the Concept Guide.

The Kahn’s Algorithm Template (BFS)

This template assumes you are given a graph as a set of vertices and a list of directed edges (the most common format in technical interviews).

/**
 * Standard Kahn's Algorithm for Topological Sort
 * @param {number} n - Number of vertices
 * @param {number[][]} edges - List of directed edges [source, destination]
 * @returns {number[]} - A valid topological order, or empty if a cycle exists
 */
function topologicalSort(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    const indegree = new Array(n).fill(0);
    const result = [];

    // 1. Build Adjacency List and Calculate Indegrees
    for (const [u, v] of edges) {
        adj[u].push(v);
        indegree[v]++;
    }

    // 2. Identify all sources (nodes with 0 prerequisites)
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (indegree[i] === 0) {
            queue.push(i);
        }
    }

    // 3. Process the queue
    while (queue.length > 0) {
        const u = queue.shift();
        result.push(u);

        for (const v of adj[u]) {
            indegree[v]--;
            // If prerequisites are satisfied, add to queue
            if (indegree[v] === 0) {
                queue.push(v);
            }
        }
    }

    // 4. Check for cycles (valid order must include all nodes)
    return result.length === n ? result : [];
}
from collections import deque

def topological_sort(n, edges):
    """
    Standard Kahn's Algorithm for Topological Sort
    :param n: Number of vertices
    :param edges: List of directed edges [source, destination]
    :return: A valid topological order, or empty if a cycle exists
    """
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    result = []

    # 1. Build Adjacency List and Calculate Indegrees
    for u, v in edges:
        adj[u].append(v)
        indegree[v] += 1

    # 2. Identify all sources (nodes with 0 prerequisites)
    queue = deque([i for i in range(n) if indegree[i] == 0])

    # 3. Process the queue
    while queue:
        u = queue.popleft()
        result.append(u)

        for v in adj[u]:
            indegree[v] -= 1
            # If prerequisites are satisfied, add to queue
            if indegree[v] == 0:
                queue.append(v)

    # 4. Check for cycles (valid order must include all nodes)
    return result if len(result) == n else []
import java.util.*;

public class TopologicalSort {
    /**
     * Standard Kahn's Algorithm for Topological Sort
     * @param n - Number of vertices
     * @param edges - List of directed edges [source, destination]
     * @return List containing a valid topological order, or empty list if cycle exists
     */
    public List<Integer> topologicalSort(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[n];
        List<Integer> result = new ArrayList<>();

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

        // 1. Build Adjacency List and Calculate Indegrees
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            indegree[edge[1]]++;
        }

        // 2. Identify all sources
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        // 3. Process the queue
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : adj.get(u)) {
                indegree[v]--;
                if (indegree[v] == 0) queue.offer(v);
            }
        }

        // 4. Check for cycles
        return result.size() == n ? result : new ArrayList<>();
    }
}
#include <vector>
#include <queue>

using namespace std;

/**
 * Standard Kahn's Algorithm for Topological Sort
 * @param n - Number of vertices
 * @param edges - List of directed edges [source, destination]
 * @return A valid topological order, or empty if a cycle exists
 */
vector<int> topologicalSort(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indegree(n, 0);
    vector<int> result;

    // 1. Build Adjacency List and Calculate Indegrees
    for (auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        indegree[edge[1]]++;
    }

    // 2. Identify all sources
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    // 3. Process the queue
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v);
        }
    }

    // 4. Check for cycles
    return result.size() == n ? result : vector<int>();
}
import "container/list"

/**
 * Standard Kahn's Algorithm for Topological Sort
 * @param n - Number of vertices
 * @param edges - List of directed edges [source, destination]
 * @returns - A valid topological order, or nil if a cycle exists
 */
func topologicalSort(n int, edges [][]int) []int {
	adj := make([][]int, n)
	indegree := make([]int, n)
	result := make([]int, 0)

	// 1. Build Adjacency List and Calculate Indegrees
	for _, edge := range edges {
		u, v := edge[0], edge[1]
		adj[u] = append(adj[u], v)
		indegree[v]++
	}

	// 2. Identify all sources
	queue := list.New()
	for i := 0; i < n; i++ {
		if indegree[i] == 0 {
			queue.PushBack(i)
		}
	}

	// 3. Process the queue
	for queue.Len() > 0 {
		element := queue.Front()
		u := element.Value.(int)
		queue.Remove(element)
		result = append(result, u)

		for _, v := range adj[u] {
			indegree[v]--
			if indegree[v] == 0 {
				queue.PushBack(v)
			}
		}
	}

	// 4. Check for cycles
	if len(result) == n {
		return result
	}
	return nil
}
# Standard Kahn's Algorithm for Topological Sort
# @param n {Integer} - Number of vertices
# @param edges {Array<Array<Integer>>} - List of directed edges [source, destination]
# @return {Array<Integer>} - A valid topological order, or empty if a cycle exists
def topological_sort(n, edges)
  adj = Hash.new { |h, k| h[k] = [] }
  indegree = Array.new(n, 0)
  result = []

  # 1. Build Adjacency List and Calculate Indegrees
  edges.each do |u, v|
    adj[u] << v
    indegree[v] += 1
  end

  # 2. Identify all sources
  queue = []
  (0...n).each do |i|
    queue << i if indegree[i] == 0
  end

  # 3. Process the queue
  while !queue.empty?
    u = queue.shift
    result << u

    adj[u].each do |v|
      indegree[v] -= 1
      queue << v if indegree[v] == 0
    end
  end

  # 4. Check for cycles
  result.length == n ? result : []
end

Code Breakdown

Key Variables

  • adj: An Adjacency List to store the graph. Mapping nodes to their dependent neighbors.
  • indegree: An array/map where indegree[i] is the number of prerequisites node i still has.
  • queue: Holds all nodes that currently have zero prerequisites remaining.
  • result: Stores the final ordered sequence.

Logic Flow 

  graph TD
    Start(Start) --> BuildGraph(Build Adj List & Count Indegrees)
    BuildGraph --> FindSources(Find all nodes with Indegree = 0)
    FindSources --> Queue{Is Queue Empty?}
    Queue -- No --> Pop(Pop Source Node)
    Pop --> AddToResult(Add to Result List)
    AddToResult --> Neighbors(Update Neighbors)
    Neighbors --> DecDegree(Indegree - 1)
    DecDegree --> NewSource{Indegree == 0?}
    NewSource -- Yes --> Push(Add to Queue)
    NewSource -- No --> Queue
    Push --> Queue
    Queue -- Yes --> CheckCycle(Result length == V?)
    CheckCycle -- Yes --> End(Return Result)
    CheckCycle -- No --> Cycle(Return NULL / Cycle Detected)
  1. Initialization: We start by converting the input edges into an adjacency list for efficient lookups and count how many incoming edges each node has.
  2. The Queue: The queue represents the set of tasks that are “ready to be performed.”
  3. Iteration: Every time we perform a task (pop from queue), we “remove” its influence from its neighbors. If a neighbor now has zero dependencies, it joins the “ready” queue.
  4. Verification: If we finish processing and the result doesn’t contain all nodes, it means we got stuck in a cycle where tasks were waiting on each other indefinitely.

Practice

Apply this template to solve these problems: