Coding

Topological sort or Kahn's algorithm

Asked at

Amazon

MicrosoftZZupee

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a Directed Acyclic Graph (DAG) with V vertices labeled from 0 to V-1.The graph is represented using an adjacency list where adj[i] lists all nodes connected to node. Find any Topological Sorting of that Graph.

In topological sorting, node u will always appear before node v if there is a directed edge from node u towards node v(u -> v).

The function should **return **an **array **representing the topological order. The output will be validated by our driver code, which checks the correctness of your topological sort. It will print **True **if the order is valid, otherwise False.

Input: V = 6,adj=[ [ ], [ ], [3], [1], [0,1], [0,2] ]

Output: [5, 4, 2, 3, 1, 0] Explanation: A graph may have multiple topological sortings.

Node 5 must appear before 0 and 2
Node 2 must appear before 3
Node 3 must appear before 1
Node 4 must appear before 0 and 1

One valid topological order is: [5, 4, 2, 3, 1, 0]

Input: V = 4, adj=[ [ ], [0], [0], [0] ]

Output: [3, 2, 1, 0] Explanation: The necessary conditions for the ordering are:

Nodes 1, 2, and 3 must all appear before 0.
Their internal order doesn’t matter.

One valid topological order is: [3, 2, 1, 0]

Input: V = 3, adj=[[1], [2], []]

1 ≤ V ≤ 10⁴
0 ≤ number of edges ≤ 10⁴

cpp

class Solution{
public:
    vector<int> topoSort(int V, vector<int> adj[]){
        
    }
};

java

class Solution {
    public int[] topoSort(int V, List<List<Integer>> adj) {
    
    }
}

python

class Solution:
    def topoSort(self, V, adj):

javascript

class Solution {
    topoSort(V, adj) {
        
    }
}

csharp

class Solution
{
    public List<int> TopoSort(int V, List<List<int>> adj)
    {

    }
}

func topoSort(V int, adj [][]int) []int {
    
}

Stuck? Show a way to structure it+

01Compute the indegree of every vertex from the adjacency list.
02Enqueue every zero-indegree vertex.
03Remove vertices, append them to the order, and release outgoing neighbors.
04Compare processed count with vertex count when cycle detection is required.

Reference answer

Compute each vertex's indegree by scanning every directed edge. Put all zero-indegree vertices into a queue. Repeatedly remove one, append it to the topological order, and decrement the indegree of every outgoing neighbor. When a neighbor reaches zero, enqueue it. In a DAG, this processes all vertices and guarantees that every edge's source appears before its destination because a vertex is emitted only after all incoming prerequisites have been removed. Time is O(V + E) and auxiliary space is O(V) beyond the graph. Although this prompt guarantees a DAG, a robust implementation can compare the output length with V; a shorter result indicates a cycle. Different queue orderings may produce different but equally valid topological orders. A min-heap instead of a queue yields the lexicographically smallest order at an added logarithmic cost.

Then expect these follow-ups

How does processed count reveal a cycle?
Tests: cycle detection
How would DFS produce a topological order?
Tests: alternative method

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question