DSA for Interviews, From Zero

Part 13 · Lesson 51 · read

Topological Sort

Put tasks in order when some depend on others, and find loops (cycles).

On this page

  1. Prerequisites are arrows
  2. Kahn's algorithm
  3. Traced: Kahn on six tasks
  4. DFS-based ordering
  5. Finding loops in directed graphs
  6. Course schedule
  7. Kahn or DFS: which one?
  8. Practice questions (7)
  9. Make it stick
  10. What's next

Prerequisites are arrows

Some jobs must happen in a set order. You put on socks before shoes. You take Algebra before Calculus. We draw this as a directed graph (lesson 49). A directed graph is a set of dots (called vertices) joined by one-way arrows. Each arrow b → a means "b must come before a". A topological order (also called topological sort) is a line-up of all the dots where every arrow points forward. For every b → a, b appears earlier than a.

Such an order exists only when the graph has no cycle. A cycle is a loop of arrows that leads back to where it started. Say A needs B, B needs C and C needs A. Nobody can go first. A directed graph with no cycle is called a DAG (directed acyclic graph, which just means "one-way arrows, no loops"). Every DAG has at least one topological order, and often many. Any valid one is fine unless the problem says otherwise.

One more word: the in-degree of a dot is the number of arrows pointing into it. Here it means the number of prerequisites the task still waits for. A task with in-degree 0 is free to start.

Check the direction
LeetCode writes [a, b] as "to take a you must first take b". So the arrow is b → a. That is the opposite of the order the numbers appear in. Reading the pair backwards is the most common mistake in this topic.
JavaScript
// "To take course a you must first take course b" is the pair [a, b].// We draw it as an arrow b -> a: b must come BEFORE a.function buildGraph(n, prerequisites) {  const graph = Array.from({ length: n }, () => []);   // graph[b] = courses that b unlocks  const indegree = new Array(n).fill(0);               // indegree[a] = how many prerequisites a still waits for  for (const [a, b] of prerequisites) {    graph[b].push(a);    indegree[a]++;  }  return { graph, indegree };}const { graph, indegree } = buildGraph(4, [[1, 0], [2, 0], [3, 1], [3, 2]]);console.log(graph);    // [ [ 1, 2 ], [ 3 ], [ 3 ], [] ]console.log(indegree); // [ 0, 1, 1, 2 ]

Kahn's algorithm

Kahn's algorithm turns a simple idea into code: "do what is ready, then see what that makes ready." A queue is a line where the first item in is the first item out. The steps:

  1. Count the in-degree of every dot.
  2. Put every dot with in-degree 0 into a queue.
  3. Take one dot from the queue and add it to the answer. Look at each dot it points to and subtract 1 from that dot's in-degree. If the number reaches 0, add that dot to the queue.
  4. Repeat until the queue is empty.

If the answer has all n dots, you have a valid order. If it is shorter, the dots left over are stuck. Each one is on a cycle, or waits for a dot that is on a cycle, so none of them ever reached in-degree 0. Use the same trick as BFS (breadth-first search): keep a head number for the front of the queue instead of removing items. This keeps the time at O(V + E), where V is the number of dots and E is the number of arrows. Every dot goes into the queue once and every arrow is looked at once.

JavaScript
// Kahn's algorithm: repeatedly take a task with nothing left to wait for.function topoSort(n, edges) {                 // each edge [from, to] means from comes before to  const graph = Array.from({ length: n }, () => []);  const indegree = new Array(n).fill(0);  for (const [from, to] of edges) {    graph[from].push(to);    indegree[to]++;  }  const queue = [];  for (let v = 0; v < n; v++) if (indegree[v] === 0) queue.push(v);   // ready right now  let head = 0;                               // dequeue by advancing an index (queue.shift() is O(n))  const order = [];  while (head < queue.length) {    const v = queue[head++];    order.push(v);    for (const next of graph[v]) {      indegree[next]--;                       // one of next's prerequisites is now done      if (indegree[next] === 0) queue.push(next);    }  }  return order.length === n ? order : [];     // fewer than n means a cycle blocked the rest}const edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];console.log(topoSort(6, edges));                 // [ 4, 5, 2, 0, 3, 1 ]console.log(topoSort(3, [[0, 1], [1, 2], [2, 0]])); // []   (a cycle: nothing can start)

Traced: Kahn on six tasks

step 1 / 27
Set up
Prepare the queue

indegree = [2,2,1,1,0,0]. This counts how many tasks each task still waits for. Task 0 waits for two tasks (5 and 4). Task 1 waits for two tasks (4 and 3). And so on.

▶const queue = [];2for (let v = 0; v < n; v++) if (indegree[v] === 0) queue.push(v);3let head = 0;4const order = [];5while (head < queue.length) {6  const v = queue[head++];7  order.push(v);8  for (const next of graph[v]) {9    indegree[next]--;10    if (indegree[next] === 0) queue.push(next);11  }12}13return order.length === n ? order : [];
Variables
indegree[2, 2, 1, 1, 0, 0]
Console
(nothing printed yet)
Watch the indegree array. A task joins the queue the moment its count hits 0. The final order is 4, 5, 2, 0, 3, 1. · interactive

DFS-based ordering

There is a second way. DFS (depth-first search) is a way to explore a graph: you follow one path as deep as you can, then go back and try another. Run DFS and write down each dot at the moment it is finished. A dot is finished when every dot it points to is already finished. So a dot always finishes after everything it unlocks. That means the finishing list is a valid order backwards. Reverse it and you have a topological order. The finishing order is called the post-order of the DFS.

To also find cycles, we give every dot one of three states. This is called a "three-colour" DFS.

Dry run · the three states of a vertex
StateMeaningIf DFS meets it
UNSEEN (0)not visited yetvisit it when we reach it
VISITING (1)on the path we are walking right nowreaching it again means there is a cycle
DONE (2)fully explored, nothing left to do heresafe to skip: it cannot lead back to where we are
JavaScript
// DFS ordering: a task is finished only after everything it unlocks is finished.// Reverse the finishing order and every prerequisite lands before the tasks that need it.function topoSortDfs(n, edges) {  const graph = Array.from({ length: n }, () => []);  for (const [from, to] of edges) graph[from].push(to);  const UNSEEN = 0, VISITING = 1, DONE = 2;   // the three colours  const state = new Array(n).fill(UNSEEN);  const finished = [];  let hasCycle = false;  function visit(v) {    state[v] = VISITING;                      // v is on the path we are walking right now    for (const next of graph[v]) {      if (state[next] === VISITING) hasCycle = true;       // we came back to the current path: a cycle      else if (state[next] === UNSEEN) visit(next);    }    state[v] = DONE;                          // everything v unlocks is already finished    finished.push(v);  }  for (let v = 0; v < n; v++) if (state[v] === UNSEEN) visit(v);  return hasCycle ? [] : finished.reverse();}const edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]];console.log(topoSortDfs(6, edges));                 // [ 5, 4, 2, 3, 1, 0 ]console.log(topoSortDfs(3, [[0, 1], [1, 2], [2, 0]])); // []

This answer is different from Kahn's ([5, 4, 2, 3, 1, 0] vs [4, 5, 2, 0, 3, 1]). Both are correct. Check any arrow, for example 2 → 3 (2 comes first in both) or 4 → 0.

Finding loops in directed graphs

In an undirected graph (every edge works both ways), meeting a dot you already visited means a cycle. The one exception is the dot you just came from. That rule is wrong for directed graphs. Look at the diamond 0 → 1 → 3 and 0 → 2 → 3. Dot 3 is reached twice, once through 1 and once through 2. Still, there is no cycle, because both arrows go the same way. "Seen before" is a cycle only if the earlier visit is still on the path we are walking now. The VISITING state remembers exactly this. A plain visited set cannot.

JavaScript
// A visited set alone is NOT a cycle detector for directed graphs.const diamond = [[1, 2], [3], [3], []];       // 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3: no cycle at allfunction wrongHasCycle(graph) {  const visited = new Set();  function visit(v) {    visited.add(v);    for (const next of graph[v]) {      if (visited.has(next)) return true;     // "seen before" is not the same as "on my current path"      if (visit(next)) return true;    }    return false;  }  return visit(0);}function hasCycle(graph) {  const state = new Array(graph.length).fill(0);   // 0 unseen, 1 on the current path, 2 finished  function visit(v) {    state[v] = 1;    for (const next of graph[v]) {      if (state[next] === 1) return true;          // only an arrow back into the current path is a cycle      if (state[next] === 0 && visit(next)) return true;    }    state[v] = 2;    return false;  }  for (let v = 0; v < graph.length; v++) if (state[v] === 0 && visit(v)) return true;  return false;}console.log(wrongHasCycle(diamond));        // true    (WRONG: 3 was reached by 1 earlier, then again by 2)console.log(hasCycle(diamond));             // false   (correct)console.log(hasCycle([[1], [2], [0]]));     // true    (0 -> 1 -> 2 -> 0)
Two ways to find a cycle
Kahn's count ("did all n dots come out?") and the three-colour DFS ("did I meet a VISITING dot?") always give the same answer. Pick the one that fits the rest of the problem.

Course schedule

Course Schedule (LeetCode 207) only asks: can every course be finished? That is the same as asking whether the prerequisite graph is a DAG. Run Kahn, then compare the number of courses you took with the total. Its sibling Course Schedule II (210) wants the actual order. Kahn already gives you that.

JavaScript
// LeetCode 207: can all courses be finished? Yes exactly when the graph has no cycle.function canFinish(numCourses, prerequisites) {  const graph = Array.from({ length: numCourses }, () => []);  const indegree = new Array(numCourses).fill(0);  for (const [course, prereq] of prerequisites) {    graph[prereq].push(course);    indegree[course]++;  }  const queue = [];  for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);  let head = 0;  while (head < queue.length) {    const c = queue[head++];    for (const next of graph[c]) {      if (--indegree[next] === 0) queue.push(next);    }  }  return head === numCourses;                 // head counts how many courses we managed to take}console.log(canFinish(2, [[1, 0]]));          // true    (take 0, then 1)console.log(canFinish(2, [[1, 0], [0, 1]]));  // false   (each needs the other first)console.log(canFinish(4, [[1, 0], [2, 1], [3, 2], [1, 3]])); // false   (1 -> 2 -> 3 -> 1 is a loop)

Kahn or DFS: which one?

Dry run · the two topological sorts side by side
Kahn (BFS-style)DFS post-order
Core ideatake away tasks that have no prerequisites leftreverse the order in which DFS finishes tasks
Data structurequeue + in-degree arrayrecursion (or a stack) + 3 states per task
Cycle detectionfewer than n tasks come out of the queuean arrow that points to a VISITING task
Gives the orderfront to back, while it runsafter reversing the finishing list
Level by level (e.g. parallel courses)easy: process the queue one round at a timeneeds extra work
Deep chainsno recursion, so no stack overflow (the call stack running out of room)recursion can overflow on chains of about 10,000 or more
Time and spaceO(V + E), O(V)O(V + E), O(V)

Kahn is the safer first choice in interviews. It uses no recursion, and the cycle check is just a count. Use the DFS version when the problem is already a DFS problem (for example 'is this node safe?').

Practice questions

First ask: what are the "tasks", and what does "must come before" mean here? Sometimes the arrows are given (courses). Sometimes you must find them yourself (alien dictionary, recipes). Sometimes the trick is to remove dots from the outside in (minimum height trees).

Q1Course scheduleMedium

There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must take course b before course a. Return true if you can finish all courses.

Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0, then course 1.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Each course needs the other one first. That is a cycle (a loop).
Example 3
Input: numCourses = 3, prerequisites = []
Output: true
Explanation: There are no prerequisites, so any order works.
Stuck? Open one hint at a time
Hint 1
Draw an arrow prerequisite → course. Which kind of graph makes it impossible to finish all courses?
Hint 2
A cycle blocks you. So the real question is: does this graph of one-way arrows contain a cycle?
Hint 3
Use Kahn's algorithm: keep taking courses that have no unfinished prerequisites. If you can take all of them, there is no cycle.
Show all 2 solutions with explanations
Approach 1Kahn's algorithm (in-degree)
The idea
  1. Build the graph with arrows prerequisite → course. Count each course's in-degree (how many prerequisites it still waits for).
  2. Put every course with in-degree 0 into a queue (a line: first in, first out).
  3. Take a course. Lower the in-degree of the courses it unlocks. Add any course that reaches 0 to the queue.
  4. Answer true if the number of courses you took equals numCourses.
JavaScript
function canFinish(numCourses, prerequisites) {  const graph = Array.from({ length: numCourses }, () => []);  const indegree = new Array(numCourses).fill(0);  for (const [course, prereq] of prerequisites) {    graph[prereq].push(course);    indegree[course]++;  }  const queue = [];  for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);  let head = 0;  while (head < queue.length) {    const c = queue[head++];    for (const next of graph[c]) {      if (--indegree[next] === 0) queue.push(next);    }  }  return head === numCourses;}console.log(canFinish(2, [[1, 0]]));         // trueconsole.log(canFinish(2, [[1, 0], [0, 1]])); // falseconsole.log(canFinish(3, []));               // true
How it works

Each course goes into the queue once and each prerequisite arrow is used once. So the time is O(V + E) and the space is O(V + E). Here V is the number of courses and E is the number of arrows. If there is a cycle, every course on it keeps an in-degree of at least 1, because it waits for the one before it in the loop. So none of them is ever taken, and the count is too small.

Approach 2DFS with three states
The idea

Walk the graph with DFS (go as deep as you can, then back up). Keep track of which courses are on the path you are walking now. If you reach a course that is still on this path, you found a cycle. Mark a finished course so you never walk it twice.

JavaScript
function canFinish(numCourses, prerequisites) {  const graph = Array.from({ length: numCourses }, () => []);  for (const [course, prereq] of prerequisites) graph[prereq].push(course);  const state = new Array(numCourses).fill(0);     // 0 unseen, 1 on the current path, 2 finished  function hasCycle(v) {    if (state[v] === 1) return true;    if (state[v] === 2) return false;    state[v] = 1;    for (const next of graph[v]) if (hasCycle(next)) return true;    state[v] = 2;    return false;  }  for (let c = 0; c < numCourses; c++) if (hasCycle(c)) return false;  return true;}console.log(canFinish(2, [[1, 0]]));         // trueconsole.log(canFinish(2, [[1, 0], [0, 1]])); // falseconsole.log(canFinish(3, []));               // true
How it works

The time is the same, O(V + E). State 2 keeps it fast. Without it, a course reachable by many paths would be explored again each time, which can take a very long time. State 1 (instead of a plain visited flag) avoids false alarms on diamond shapes.

Which approach should you use?

Kahn's version has no recursion and gives you the order for free, so it works directly for the next problem. The DFS version is the classic way to test for a cycle. (LeetCode 207.)

Q2Course schedule IIMedium

Same setup as the previous question. Return an order of the courses that follows every prerequisite. If several orders work, return any of them. If none works, return an empty array.

Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: 0 first, then 1.
Example 2
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: 0 unlocks 1 and 2. Both must be done before 3. [0,2,1,3] is also valid.
Example 3
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: []
Explanation: There is a cycle, so no valid order exists.
Stuck? Open one hint at a time
Hint 1
This is question 1, but now you must return the order itself.
Hint 2
The order in which Kahn's algorithm takes the courses is already a valid schedule.
Hint 3
If fewer than numCourses courses came out, return an empty array.
Show all 2 solutions with explanations
Approach 1Kahn's algorithm
The idea

Run Kahn's algorithm. Write down every course as it leaves the queue.

JavaScript
function findOrder(numCourses, prerequisites) {  const graph = Array.from({ length: numCourses }, () => []);  const indegree = new Array(numCourses).fill(0);  for (const [course, prereq] of prerequisites) {    graph[prereq].push(course);    indegree[course]++;  }  const queue = [];  for (let c = 0; c < numCourses; c++) if (indegree[c] === 0) queue.push(c);  let head = 0;  while (head < queue.length) {    const c = queue[head++];    for (const next of graph[c]) {      if (--indegree[next] === 0) queue.push(next);    }  }  return queue.length === numCourses ? queue : [];   // the queue ends up holding the order}console.log(findOrder(2, [[1, 0]]));                             // [ 0, 1 ]console.log(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]));     // [ 0, 1, 2, 3 ]console.log(findOrder(2, [[1, 0], [0, 1]]));                     // []
How it works

We never remove anything from the queue array. We only move head. So after the loop the array holds every course in the order it was processed. The time is O(V + E).

Approach 2DFS post-order, reversed
The idea

Start a DFS from every course you have not seen yet, following arrows prerequisite → course. Add a course to a list when it finishes. The reversed list is the schedule. If you meet a course that is still on the current path, there is a cycle.

JavaScript
function findOrder(numCourses, prerequisites) {  const graph = Array.from({ length: numCourses }, () => []);  for (const [course, prereq] of prerequisites) graph[prereq].push(course);  const state = new Array(numCourses).fill(0);     // 0 unseen, 1 on the current path, 2 finished  const finished = [];  let cycle = false;  function visit(v) {    state[v] = 1;    for (const next of graph[v]) {      if (state[next] === 1) cycle = true;      else if (state[next] === 0) visit(next);    }    state[v] = 2;    finished.push(v);  }  for (let c = 0; c < numCourses; c++) if (state[c] === 0) visit(c);  return cycle ? [] : finished.reverse();}console.log(findOrder(2, [[1, 0]]));                             // [ 0, 1 ]console.log(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]));     // [ 0, 2, 1, 3 ]console.log(findOrder(2, [[1, 0], [0, 1]]));                     // []
How it works

A course finishes only after every course it unlocks has finished. So after reversing, each prerequisite comes before the courses it unlocks. The time is O(V + E). This order is different from Kahn's order, and both are accepted.

Which approach should you use?

Kahn's is shorter and uses a loop instead of recursion. Know the DFS one too, for problems that are already DFS problems. (LeetCode 210.)

Q3Find eventual safe statesMedium

A directed graph has n nodes. graph[i] lists the nodes that i has an arrow to. A node is terminal if it has no outgoing arrows. A node is safe if every path that starts from it leads to a terminal node. Return all safe nodes in ascending order.

Example 1
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: 5 and 6 have no outgoing arrows (they are terminal). 2 and 4 lead only to 5. Nodes 0, 1, 3 can reach the cycle 0 → 1 → 3 → 0.
Example 2
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation: Node 1 points to itself. Every other node (except 4) can reach it or the loop 0 → 2 → 3 → 0.
Stuck? Open one hint at a time
Hint 1
graph[i] lists the nodes that i points to. A node is safe if every path that starts from it ends at a terminal node (a node with no outgoing arrows).
Hint 2
A node is unsafe exactly when it can reach a cycle. So you are looking for the nodes that cannot reach one.
Hint 3
Flip the question. Start from the terminal nodes and spread backwards along the arrows. When can you say a node is safe?
Show all 2 solutions with explanations
Approach 1DFS with colours
The idea

Run the three-state DFS. A node is safe when all the nodes it points to are safe. If the DFS meets a node that is still on the current path, or one already known to be unsafe, then the node you started from is unsafe.

JavaScript
function eventualSafeNodes(graph) {  const n = graph.length;  const state = new Array(n).fill(0);     // 0 unseen, 1 on the path or unsafe, 2 safe  function isSafe(v) {    if (state[v] !== 0) return state[v] === 2;    state[v] = 1;                         // stays 1 if we return false: that marks "unsafe"    for (const next of graph[v]) if (!isSafe(next)) return false;    state[v] = 2;    return true;  }  const result = [];  for (let v = 0; v < n; v++) if (isSafe(v)) result.push(v);  return result;}console.log(eventualSafeNodes([[1, 2], [2, 3], [5], [0], [5], [], []]));         // [ 2, 4, 5, 6 ]console.log(eventualSafeNodes([[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]));      // [ 4 ]
How it works

Every node is explored at most once because we remember its state. So the time is O(V + E). We leave state 1 on purpose when a node fails. A node on a cycle, or one that leads into a cycle, must never be called safe later.

Approach 2Reverse graph + Kahn on out-degree
The idea
  1. Reverse every arrow. Also record each node's out-degree (the number of arrows going out of it in the original graph).
  2. Start the queue with the terminal nodes (out-degree 0).
  3. When a node is safe, every node that pointed to it has one less unsettled arrow. When a node reaches out-degree 0, it is safe too.
JavaScript
function eventualSafeNodes(graph) {  const n = graph.length;  const reverse = Array.from({ length: n }, () => []);  const outdeg = new Array(n).fill(0);  for (let v = 0; v < n; v++) {    outdeg[v] = graph[v].length;    for (const next of graph[v]) reverse[next].push(v);  }  const queue = [];  for (let v = 0; v < n; v++) if (outdeg[v] === 0) queue.push(v);  const safe = new Array(n).fill(false);  let head = 0;  while (head < queue.length) {    const v = queue[head++];    safe[v] = true;    for (const prev of reverse[v]) {      if (--outdeg[prev] === 0) queue.push(prev);    }  }  const result = [];  for (let v = 0; v < n; v++) if (safe[v]) result.push(v);   // already in ascending order  return result;}console.log(eventualSafeNodes([[1, 2], [2, 3], [5], [0], [5], [], []]));         // [ 2, 4, 5, 6 ]console.log(eventualSafeNodes([[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]));      // [ 4 ]
How it works

This is topological sort on the reversed graph. The nodes that can never be taken away are exactly the ones that reach a cycle. The time is O(V + E), it uses a loop instead of recursion, and the answer is easy to put in order by scanning the numbers.

Which approach should you use?

Both are O(V + E). The DFS is short. The reversed Kahn avoids recursion. (LeetCode 802. A related problem is 1462, Course Schedule IV, which asks whether one course can reach another.)

Q4Alien dictionary (premium)Hard

A new language uses the lowercase English letters, but in an unknown order. You are given words, a list sorted in dictionary order of that alphabet. Return a string of the letters that appear, in a valid order for the alien alphabet. If the input contradicts itself, return an empty string. If several orders are valid, return any of them.

Example 1
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: Compare each word with the next one. wrt<wrf gives t before f. wrf<er gives w before e. er<ett gives r before t. ett<rftt gives e before r. So the order is w, e, r, t, f.
Example 2
Input: words = ["z","x"]
Output: "zx"
Explanation: z comes before x.
Example 3
Input: words = ["z","x","z"]
Output: ""
Explanation: z must be before x and x must be before z. That cannot be true.
Example 4
Input: words = ["abc","ab"]
Output: ""
Explanation: A longer word cannot come before its own start (prefix).
Stuck? Open one hint at a time
Hint 1
Each pair of next-to-each-other words tells you at most one fact about the alphabet. Which letters show that fact?
Hint 2
Compare two next-to-each-other words letter by letter. At the first place where they differ, the letter in the first word comes before the letter in the second word.
Hint 3
Treat those facts as arrows between letters. Then do a topological sort of the letters. Watch out for the prefix trap (a longer word before its own start) and for cycles.
Show all 2 solutions with explanations
Approach 1Build edges, then Kahn's algorithm
The idea
  1. Collect every letter that appears. Each letter is one vertex (one dot in the graph).
  2. For each pair of next-to-each-other words, find the first place where they differ. Add an arrow earlier → later (only once). If the second word is the first word's own start (a prefix) and is shorter, the input is invalid. Return an empty string.
  3. Run Kahn's algorithm. If not every letter comes out, there is a cycle. Return an empty string.
JavaScript
function alienOrder(words) {  const edges = new Map();                         // letter -> set of letters that must come after it  const indegree = new Map();  for (const word of words) {    for (const ch of word) {      if (!edges.has(ch)) { edges.set(ch, new Set()); indegree.set(ch, 0); }    }  }  for (let i = 0; i + 1 < words.length; i++) {    const a = words[i], b = words[i + 1];    if (a.length > b.length && a.startsWith(b)) return "";   // "abc" before "ab" is impossible    for (let j = 0; j < Math.min(a.length, b.length); j++) {      if (a[j] !== b[j]) {        if (!edges.get(a[j]).has(b[j])) {          edges.get(a[j]).add(b[j]);          indegree.set(b[j], indegree.get(b[j]) + 1);        }        break;                                     // later letters tell us nothing      }    }  }  const queue = [];  for (const [ch, deg] of indegree) if (deg === 0) queue.push(ch);  let head = 0;  while (head < queue.length) {    const ch = queue[head++];    for (const next of edges.get(ch)) {      indegree.set(next, indegree.get(next) - 1);      if (indegree.get(next) === 0) queue.push(next);    }  }  return queue.length === edges.size ? queue.join("") : "";}console.log(alienOrder(["wrt", "wrf", "er", "ett", "rftt"])); // wertfconsole.log(alienOrder(["z", "x"]));                          // zxconsole.log(alienOrder(["z", "x", "z"]));                     // (empty string)console.log(alienOrder(["abc", "ab"]));                       // (empty string)
How it works

The time is O(L + C + E). L is the total number of characters in all words. C is the number of different letters. E is the number of different arrows. Building the arrows reads each pair of next-to-each-other words once. Kahn takes time in line with the letters and arrows. Only the first difference between two words counts. The letters after it say nothing about the order. Letters with no rules can go anywhere, so several answers can be valid.

Approach 2Build edges, then DFS post-order
The idea

Build the same graph. Then run the three-state DFS and reverse the finishing order. If you meet a letter that is on the current path, there is a cycle.

JavaScript
function alienOrder(words) {  const edges = new Map();  for (const word of words) for (const ch of word) if (!edges.has(ch)) edges.set(ch, new Set());  for (let i = 0; i + 1 < words.length; i++) {    const a = words[i], b = words[i + 1];    if (a.length > b.length && a.startsWith(b)) return "";    for (let j = 0; j < Math.min(a.length, b.length); j++) {      if (a[j] !== b[j]) { edges.get(a[j]).add(b[j]); break; }    }  }  const state = new Map();                         // missing = unseen, 1 = on the path, 2 = finished  const finished = [];  function visit(ch) {                             // returns false when a cycle is found    state.set(ch, 1);    for (const next of edges.get(ch)) {      if (state.get(next) === 1) return false;      if (!state.has(next) && !visit(next)) return false;    }    state.set(ch, 2);    finished.push(ch);    return true;  }  for (const ch of edges.keys()) if (!state.has(ch) && !visit(ch)) return "";  return finished.reverse().join("");}console.log(alienOrder(["wrt", "wrf", "er", "ett", "rftt"])); // wertfconsole.log(alienOrder(["z", "x"]));                          // zxconsole.log(alienOrder(["z", "x", "z"]));                     // (empty string)console.log(alienOrder(["abc", "ab"]));                       // (empty string)
How it works

The graph and the time are the same. A Set for each letter's outgoing arrows removes repeats, for example when two pairs both say a is before b.

Which approach should you use?

Kahn's is the usual interview answer, because the cycle check is just a count. Two traps make most attempts fail: the prefix case and counting the same arrow twice. This is a premium (paid) problem on LeetCode (269, "Alien Dictionary"). The statement is copied here.

Q5Minimum height treesMedium

A tree is a connected graph with no cycles. You get n nodes labelled 0..n-1 and a list of edges (links with no direction). You may choose any node as the root. The height of a rooted tree is the number of edges on the longest path going down from the root. Return the labels of every root that gives the smallest height, in any order.

Example 1
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: With 1 as the root, the tree has height 1. With any other root, the height is 2.
Example 2
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Explanation: Both 3 and 4 give height 2, which is the smallest possible.
Example 3
Input: n = 1, edges = []
Output: [0]
Explanation: There is only one node.
Stuck? Open one hint at a time
Hint 1
The graph is a tree. Pick a node as the root and measure the tallest branch. That is the height for that root. Which roots give the smallest height?
Hint 2
Trying every root works but costs O(n²). Where would a good root be: near the leaves or near the middle?
Hint 3
Remove all the leaves (nodes with only one neighbour). Then remove the new leaves, and so on, like Kahn's algorithm working inwards. What is left at the end?
Show all 2 solutions with explanations
Approach 1Brute force: BFS from every node
The idea

Use each node as the root, one by one. Run BFS (visit level by level) and count the levels. That count is the height. Keep the roots whose height equals the smallest one.

JavaScript
function findMinHeightTrees(n, edges) {  const graph = Array.from({ length: n }, () => []);  for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); }  function height(root) {    const seen = new Array(n).fill(false);    seen[root] = true;    let level = [root], h = -1;    while (level.length) {      h++;      const next = [];      for (const v of level) for (const w of graph[v]) if (!seen[w]) { seen[w] = true; next.push(w); }      level = next;    }    return h;  }  let best = Infinity, result = [];  for (let r = 0; r < n; r++) {    const h = height(r);    if (h < best) { best = h; result = [r]; }    else if (h === best) result.push(r);  }  return result;}console.log(findMinHeightTrees(4, [[1, 0], [1, 2], [1, 3]]));                         // [ 1 ]console.log(findMinHeightTrees(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]));         // [ 3, 4 ]console.log(findMinHeightTrees(1, []));                                               // [ 0 ]
How it works

One BFS takes O(n) time and we run n of them, so the total is O(n²). It is correct, but too slow when n is up to 20,000.

Approach 2Remove the leaves layer by layer (topological idea)
The idea
  1. A node's degree is its number of neighbours. A leaf has degree 1.
  2. Remove all current leaves at once (one "layer"). This lowers the degree of their neighbours. Neighbours that become leaves form the next layer.
  3. Stop when 2 or fewer nodes remain. These are the centre of the tree, and they are the answer.
JavaScript
function findMinHeightTrees(n, edges) {  if (n <= 2) return Array.from({ length: n }, (_, i) => i);  const graph = Array.from({ length: n }, () => []);  const degree = new Array(n).fill(0);  for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); degree[a]++; degree[b]++; }  let leaves = [];  for (let v = 0; v < n; v++) if (degree[v] === 1) leaves.push(v);  let remaining = n;  while (remaining > 2) {    remaining -= leaves.length;               // delete this whole layer    const nextLeaves = [];    for (const leaf of leaves) {      for (const nb of graph[leaf]) {        if (--degree[nb] === 1) nextLeaves.push(nb);   // nb has become a leaf      }    }    leaves = nextLeaves;  }  return leaves;}console.log(findMinHeightTrees(4, [[1, 0], [1, 2], [1, 3]]));                         // [ 1 ]console.log(findMinHeightTrees(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]));         // [ 3, 4 ]console.log(findMinHeightTrees(1, []));                                               // [ 0 ]
How it works

Each node is removed once and each edge is looked at twice. So the time and space are O(n). The last one or two nodes are the middle of the longest path. That is why they give the smallest height. A tree has at most two such centres, so the loop can stop when 2 or fewer nodes remain.

Which approach should you use?

Use the layer-removing method. It works like Kahn's algorithm on a tree with no arrow directions. The brute force is useful to check small inputs. (LeetCode 310.)

Q6Parallel courses (premium)Medium

You are given n courses labelled 1..n and relations. A pair [prev, next] means course prev must be finished before next starts. In one semester you can take any number of courses, as long as you finished all their prerequisites in earlier semesters. Return the smallest number of semesters needed to take every course. Return -1 if it is impossible.

Example 1
Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: Semester 1: courses 1 and 2 together. Semester 2: course 3.
Example 2
Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: There is a cycle, so no course in it can ever start.
Example 3
Input: n = 4, relations = [[1,2],[2,3],[1,4]]
Output: 3
Explanation: The chain 1 → 2 → 3 needs three semesters. Course 4 fits in at the same time.
Stuck? Open one hint at a time
Hint 1
Each pair [prev, next] is an arrow prev → next. In one semester you may take every course whose prerequisites are all done.
Hint 2
Kahn's algorithm already frees courses in "waves". What does one wave match?
Hint 3
The answer is the number of waves. This equals the length of the longest chain of prerequisites. If a cycle blocks some courses, return -1.
Show all 2 solutions with explanations
Approach 1Kahn's algorithm, one semester per round
The idea

Process the queue one whole level at a time. Each level is one semester. Count the semesters and the courses taken. If you did not take all courses, there is a cycle.

JavaScript
function minimumSemesters(n, relations) {  const graph = Array.from({ length: n + 1 }, () => []);   // courses are numbered from 1  const indegree = new Array(n + 1).fill(0);  for (const [prev, next] of relations) { graph[prev].push(next); indegree[next]++; }  let current = [];  for (let c = 1; c <= n; c++) if (indegree[c] === 0) current.push(c);  let semesters = 0, taken = 0;  while (current.length) {    semesters++;    const nextRound = [];    for (const c of current) {      taken++;      for (const next of graph[c]) if (--indegree[next] === 0) nextRound.push(next);    }    current = nextRound;  }  return taken === n ? semesters : -1;}console.log(minimumSemesters(3, [[1, 3], [2, 3]]));                 // 2console.log(minimumSemesters(3, [[1, 2], [2, 3], [3, 1]]));         // -1console.log(minimumSemesters(4, [[1, 2], [2, 3], [1, 4]]));         // 3
How it works

Each course is taken in the earliest semester in which all its prerequisites are finished. So the number of rounds equals the length of the longest prerequisite chain (counted in courses). The time is O(n + E).

Approach 2DFS: longest chain with saved answers
The idea

The earliest semester for a course is 1 + the biggest earliest-semester among its prerequisites. Work this out with DFS and save each answer so you do not repeat work (a cache). Use three states to find a cycle.

JavaScript
function minimumSemesters(n, relations) {  const prereqs = Array.from({ length: n + 1 }, () => []);   // prereqs[c] = courses needed before c  for (const [prev, next] of relations) prereqs[next].push(prev);  const state = new Array(n + 1).fill(0);       // 0 unseen, 1 on the path, 2 done  const semester = new Array(n + 1).fill(0);    // earliest semester for each course, once done  function earliest(c) {                        // returns -1 if a cycle is found    if (state[c] === 2) return semester[c];    if (state[c] === 1) return -1;    state[c] = 1;    let best = 0;    for (const p of prereqs[c]) {      const s = earliest(p);      if (s === -1) return -1;      best = Math.max(best, s);    }    state[c] = 2;    semester[c] = best + 1;    return semester[c];  }  let answer = 0;  for (let c = 1; c <= n; c++) {    const s = earliest(c);    if (s === -1) return -1;    answer = Math.max(answer, s);  }  return answer;}console.log(minimumSemesters(3, [[1, 3], [2, 3]]));                 // 2console.log(minimumSemesters(3, [[1, 2], [2, 3], [3, 1]]));         // -1console.log(minimumSemesters(4, [[1, 2], [2, 3], [1, 4]]));         // 3
How it works

Memoization is a technique that saves (remembers) the result of a call, so the same call is never worked out twice. Here it means each course is worked out only once. The time is O(n + E). This is the idea of the longest path in a DAG. It only works because the graph has no cycles.

Which approach should you use?

Kahn level by level is the cleaner choice, because the number of rounds is the answer. This is a premium (paid) problem on LeetCode (1136, "Parallel Courses"). The statement is copied here.

Q7Find all possible recipes from given suppliesMedium

You have recipes[i]. Each one needs the ingredients listed in ingredients[i]. You also start with a list of supplies (you have as many of each as you need). An ingredient can be another recipe. All recipe names and supplies are different from each other. Return every recipe you can make, in any order.

Example 1
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation: Both ingredients are in the supplies.
Example 2
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation: Make the bread first. Then the sandwich uses the bread and the meat.
Example 3
Input: recipes = ["a","b"], ingredients = [["b"],["a"]], supplies = []
Output: []
Explanation: a needs b and b needs a, so neither can start.
Stuck? Open one hint at a time
Hint 1
You can make a recipe once all its ingredients are available. An ingredient is either a supply or another recipe.
Hint 2
Draw an arrow ingredient → recipe. What works like the in-degree (the number of things it waits for) of a recipe?
Hint 3
Start the queue with the supplies. Each time an item becomes available, tell every recipe that uses it.
Show all 2 solutions with explanations
Approach 1Repeat until nothing changes
The idea

Keep a set of the items you have (the supplies). Go over all recipes again and again. Whenever all ingredients of a recipe are available, make it and add it to the set. Stop after a pass in which no new recipe was made.

JavaScript
function findAllRecipes(recipes, ingredients, supplies) {  const have = new Set(supplies);  const made = new Array(recipes.length).fill(false);  const result = [];  let changed = true;  while (changed) {    changed = false;    for (let i = 0; i < recipes.length; i++) {      if (made[i]) continue;      if (ingredients[i].every((x) => have.has(x))) {        made[i] = true;        have.add(recipes[i]);        result.push(recipes[i]);        changed = true;      }    }  }  return result;}console.log(findAllRecipes(["bread"], [["yeast", "flour"]], ["yeast", "flour", "corn"]));                         // [ 'bread' ]console.log(findAllRecipes(["bread", "sandwich"], [["yeast", "flour"], ["bread", "meat"]], ["yeast", "flour", "meat"])); // [ 'bread', 'sandwich' ]console.log(findAllRecipes(["a", "b"], [["b"], ["a"]], []));                                                     // []
How it works

Each pass costs the total number of ingredients (I). In the worst case there are as many passes as recipes (R). So the time is O(R × I). This is fine for small inputs, but it keeps checking recipes that are far from ready.

Approach 2Kahn's algorithm from the supplies
The idea
  1. For each ingredient, remember which recipes need it. For each recipe, count its ingredients. This count is its in-degree.
  2. Put all supplies in the queue.
  3. Take an item from the queue. For each recipe that needs it, lower that recipe's count by 1. At 0, you can make the recipe. Save it in the answer and add it to the queue, because other recipes may need it.
JavaScript
function findAllRecipes(recipes, ingredients, supplies) {  const neededBy = new Map();                    // item -> recipes that use it  const missing = new Map();                     // recipe -> ingredients still unavailable  for (let i = 0; i < recipes.length; i++) {    missing.set(recipes[i], ingredients[i].length);    for (const item of ingredients[i]) {      if (!neededBy.has(item)) neededBy.set(item, []);      neededBy.get(item).push(recipes[i]);    }  }  const queue = [...supplies];  let head = 0;  const result = [];  while (head < queue.length) {    const item = queue[head++];    for (const recipe of neededBy.get(item) || []) {      missing.set(recipe, missing.get(recipe) - 1);      if (missing.get(recipe) === 0) { result.push(recipe); queue.push(recipe); }    }  }  return result;}console.log(findAllRecipes(["bread"], [["yeast", "flour"]], ["yeast", "flour", "corn"]));                         // [ 'bread' ]console.log(findAllRecipes(["bread", "sandwich"], [["yeast", "flour"], ["bread", "meat"]], ["yeast", "flour", "meat"])); // [ 'bread', 'sandwich' ]console.log(findAllRecipes(["a", "b"], [["b"], ["a"]], []));                                                     // []
How it works

Each ingredient entry is used once, so the time is O(S + R + I). A recipe on a cycle, or one that needs something nobody supplies, never reaches count 0. It is simply never reported, so you need no separate cycle check.

Which approach should you use?

Use Kahn's algorithm. It runs in linear time instead of repeated passes, and the supplies act as the vertices with in-degree 0. (LeetCode 2115.)

Make it stick

Make it stick — close this page, then
  1. Say what a topological order and a DAG are, and which graphs have no valid order.
  2. Write Kahn's algorithm from memory, including the cycle check.
  3. Explain the three DFS states and why reversing the finish order works.
  4. Explain why a plain visited set gives a wrong cycle answer on a directed diamond.
  5. Say which way the arrow points for the pair [a, b] in Course Schedule.
  6. Name two problems where you must build the graph from other data first.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

So far every arrow counted the same, or had no length at all. In Lesson 52 arrows get costs. You will use BFS when all costs are equal. Then you will use Dijkstra with a priority queue (a line where the smallest item always comes out first) to find the cheapest route. Last comes Bellman–Ford, for when the number of stops is limited.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series