Course Schedule I

Hard

Finishable exactly when there is no cycle

Problem

Given numCourses and prerequisite pairs, decide whether you can finish all courses — i.e. whether the directed graph has no cycle.

In simple words

Peel off courses with no remaining prerequisites (Kahn's algorithm); if all get taken, it's doable.

The idea

Prerequisites form a directed graph and a valid order exists precisely when that graph is acyclic. Run Kahn's algorithm and check whether every course was emitted; anything left over sits in a cycle.

The trick

Edge direction: prerequisite -> course.
Count the ordered courses; less than numCourses means a cycle.
O(V + E).

←→stepspaceplay

indegrees[0,1,2,1]

1/6

Optimal

timeO(V+E)spaceO(V+E)

Cycle ⇒ impossible.

1q = every course whose indegree is 02while q not empty:3  c = q.pop(); processed += 14  for nb in adj[c]: indeg[nb] -= 1; if now 0, q.push(nb)5return processed == numCourses

Input

nodes: 4, 4 edges

Memory

indegrees: [0,1,2,1]
processed: —

Output

finish: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 2, prerequisites = [[1,0]]
Output:: true
Explanation:: Take 0 then 1 — no deadlock.

Example 2

Input:: n = 2, prerequisites = [[1,0],[0,1]]
Output:: false
Explanation:: They need each other → impossible.

Example 3

Input:: n = 3, prerequisites = [[1,0],[2,1]]
Output:: true
Explanation:: A clean chain works.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.