Get started

Topological Sort Coding Problems: 11 Questions with Solutions

11 topological sort coding problems — 8 medium · 3 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.

  • Problems: 11
  • By difficulty: 8 medium · 3 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

An ordering of a directed acyclic graph in which every edge points forward: course prerequisites, build dependencies, task ordering. Kahn's algorithm (repeatedly take a node with no remaining incoming edges) and the DFS post-order both produce one and both detect a cycle when they cannot; these problems practise both.

How topological sort works, step by step

0in=01in=02in=03in=04in=05in=0queueemptyorder452031
Ordering courses after their prerequisites, with Kahn's topological sort. Example: numCourses = 6, prerequisites = [[2,5], [0,5], [0,4], [1,4], [3,2], [1,3]]
  1. An arrow b → a means course b must be taken before a, so a course's in-degree counts its unmet prerequisites. Courses 4 and 5 have in-degree 0 and can be taken now, so they start the queue.
  2. Take 4 off the queue and append it to the order. Crossing off its arrows lowers 0's in-degree to 1 and 1's to 1; none reaches 0 yet, so nothing joins the queue.
  3. Take 5 off the queue and append it to the order. Crossing off its arrows lowers 2's in-degree to 0 and 0's to 0; 2 and 0 reach 0 and join the queue. A course is queued the moment its last prerequisite is placed, never earlier.
  4. Take 2 off the queue and append it to the order. Crossing off its arrows lowers 3's in-degree to 0; 3 reaches 0 and joins the queue.
  5. Take 0 off the queue and append it to the order. No course lists 0 as a prerequisite, so no in-degree changes; 3 is next.
  6. Take 3 off the queue and append it to the order. Crossing off its arrows lowers 1's in-degree to 0; 1 reaches 0 and joins the queue.
  7. Take 1 off the queue and append it to the order. No course lists 1 as a prerequisite, so no in-degree changes.
  8. The order 4, 5, 2, 0, 3, 1 puts every course after all its prerequisites. All 6 courses came out, which also proves there is no cycle: a course on a cycle never reaches in-degree 0. Each course and arrow is handled once, O(V + E).

Topological Sort study plan

10 of the 11 Topological Sort problems (7 medium and 3 hard) over 7 days, about 6 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 1 in the full list below are practice at your own pace. Then move on to Union Find.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 6

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Union Find

Topological Sort: the essentials

When to reach for it

"Prerequisites", "dependencies", "must come before", "an order in which to run the tasks", "can all the courses be finished" — a directed graph where you need an order consistent with every edge, or proof that none exists. Also dynamic programming over a directed acyclic graph: the longest path, the number of routes, or the earliest round each task can run, each computed in topological order.

The pattern

Kahn's algorithm suits most of these. Count in-degrees, start with every node of in-degree 0, and repeatedly take one, append it to the order and decrement its neighbours' in-degrees, adding any that reach 0. If the order ends with fewer than n nodes, the rest lie on a cycle or behind one. Taking the ready nodes one layer at a time gives the fewest rounds when independent tasks can run together.

def topo_order(n, edges):           # edge (a, b): a must come before b
    adj, indeg = [[] for _ in range(n)], [0] * n
    for a, b in edges:
        adj[a].append(b)
        indeg[b] += 1
    order = [i for i in range(n) if indeg[i] == 0]
    for u in order:                 # the list grows as nodes are freed
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                order.append(v)
    return order if len(order) == n else []     # [] means a cycle

Cost

O(V + E) time and space, for Kahn's algorithm and for the depth-first version alike.

Common mistakes

  • Edge direction: in Course Schedule, [a, b] means b is taken before a; building it the other way round still finds cycles but gives the order reversed.
  • Starting from one node of in-degree 0 instead of all of them.
  • In the depth-first version, a single visited set, which cannot tell a back edge (a cycle) from a finished node.
  • Assuming the order is unique; when the smallest order in dictionary order is wanted, use a heap in place of the queue.

Start with

All topological sort problems

Medium (8)

Hard (3)

Companies that ask topological sort problems

  • Amazon 9 problems on topological sort
  • Google 9 problems on topological sort
  • Adobe 3 problems on topological sort
  • Microsoft 2 problems on topological sort
  • Bloomberg 1 problem on topological sort
  • Flipkart 1 problem on topological sort
  • Meta 1 problem on topological sort

Next topic: Union Find