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

LeetCode #207Medium
Can you finish? = is it a DAG (no cycle)?

Given a number of courses and a list of prerequisite pairs, determine whether it is possible to finish all courses (i.e. the prerequisite graph contains no cycle).

Asked atAmazonGoogleMetaMicrosoft
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 (topological sort by in-degree)
▸
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
4processed = 0
5while queue not empty:
6    u = pop; processed += 1
7    for u → v: in-deg[v] -= 1; if 0: push v
8return processed == numCourses   // all drained = DAG
state
  • numCourses4
  • answer?= is it a DAG

line 1Course Schedule: with numCourses = 4 and prerequisites [[1,0],[2,0],[3,1],[3,2]], can you finish every course? Each pair [a, b] reads "b is a prerequisite of a", so we draw the edge b → a — the arrow points the way you progress. The whole question reduces to one thing: is this graph a DAG (no cycle)? If a cycle exists, two courses each wait on the other forever, and you can never start.