Course Schedule

Difficulty: Medium

Problem

There are numCourses courses labeled 0 to numCourses − 1, and a list prerequisites where prerequisites[i] = [a, b] means you MUST take course b before course a. Return true if it is possible to finish ALL courses. Under the hood this is a DIRECTED graph question: each pair [a, b] is an arrow b → a, and the real question is whether that graph contains a CYCLE. Compare [[1,0]] (take 0, then 1 — fine) with [[1,0],[0,1]]: course 1 waits for 0 while course 0 waits for 1. Each is stuck behind the other — a deadlock — so the answer is false.

Example

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: [1,0] means 'take course 0 before course 1'. Take 0 first, then 1 — both courses finished, so true.

Brute-force approach

You could hunt for a cycle by hand — DFS from every course and watch for a repeat — but the clean beginner path IS the optimal one: Kahn's peel-off detects the cycle simply by 'taking' courses. We go straight to it.

Optimal approach

Key insight: Repeatedly take any course with zero unmet prerequisites and dissolve its arrows. If everyone eventually gets taken, there was no cycle. If the queue dries up early, the survivors are deadlocked.

Turn each pair [a, b] into an arrow b → a, count every course's unmet prerequisites (indegree), then repeatedly take any indegree-0 course and cut its outgoing arrows. All courses taken ⟺ no cycle.

Steps

  1. Build the graph: for each [a, b], add the arrow b → a and do indegree[a] += 1
  2. Seed a queue with EVERY course whose indegree is 0 — they are takeable immediately
  3. Pop a course, count it as taken, and decrement the indegree of every course it unlocks
  4. Whenever a dependent's indegree hits exactly 0, it joins the queue
  5. Verdict: taken == numCourses means no cycle → true; anything less means a deadlock → false

Time complexity: O(V + E) · Space complexity: O(V + E)