Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Course Schedule II

LeetCode #210Medium
Return a valid topological order

Given a number of courses and their prerequisite pairs, return an ordering in which all courses can be taken. If no valid ordering exists (the graph has a cycle), return an empty list.

Asked atAmazonMetaGoogle
step 1 / 16
prerequisite graph (b → a = take b first)
0
1
2
3
adjacency list
  • 0:[1, 2]
  • 1:[3]
  • 2:[3]
  • 3:[]
in-degree (prereqs left)
coursein-degdone
00
10
20
30
queue · in-degree 0
(empty)
Kahn's algorithm — collect the pop order
▸
1build graph; edge b → a for prereq [a, b]
2in-deg[v] = number of edges into v
3queue = all v with in-deg[v] == 0
4order = []
5while queue not empty:
6    u = pop; order.append(u)
7    for u → v: in-deg[v] -= 1; if 0: push v
8return len(order) == numCourses ? order : []
state
  • numCourses4
  • goala valid topo order

line 1Course Schedule II: same graph, but now return a VALID ORDER to take all 4 courses. Pair [a, b] means "take b before a", drawn as edge b → a. A topological order is any listing of the nodes where every edge points forward — no course appears before a prerequisite. Kahn's algorithm builds exactly such an order for free: the sequence in which we pop ready courses IS a topological sort.