Course Schedule

Difficulty: Medium

Problem

There are numCourses courses numbered 0 through numCourses − 1, plus a list prerequisites in which each pair [a, b] means course b has to be finished before course a. Decide whether it is possible to complete every course. Think of each pair as a DIRECTED edge b → a; the question becomes whether the graph has a CYCLE. For instance, [[1,0]] is fine (0, then 1), but [[1,0],[0,1]] is a deadlock where each course waits for the other, so the answer is false.

Example

Input: numCourses = 3, prerequisites = [[1,0],[2,1]]
Output: true
Explanation: The pairs form a chain 0 → 1 → 2 with no cycle. Take course 0, then 1, then 2, and everything is finished, so the answer is true.

Brute-force approach

The honest brute force is the audit: try every order of the courses and check each prerequisite arrow against the order (b must come before a for every pair [a, b]); if some order passes, the answer is true. It is right, but the number of orders is n factorial. On the chain 0 -> 1 -> 2 there are 3! = 6 orders and, at 2 arrow checks each, at most 6 x 2 = 12 checks, and only one order (0, 1, 2) passes. With 10 courses there are 10! = 3,628,800 orders (32,659,200 checks for 9 arrows). Kahn's peel never tries an order: it takes a course whose prerequisites are all done, cuts its arrows, and repeats, O(V + E).

Time complexity: O(n! x E): 6 orders and 12 checks for 3 courses, 3,628,800 orders for 10 · Space complexity: O(n) for one order at a time

Trade-offs

The number of orders is n factorial: 3,628,800 for just 10 courses
Throws away what an order already proved; Kahn's peel builds one valid order instead of testing them all

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

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

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

Pseudocode

function canFinish(numCourses, prerequisites):
    adj = numCourses empty lists
    indegree = numCourses zeros
    
    for each [a, b] in prerequisites:
        adj[____].append(____)          // the arrow leaves the prerequisite
        indegree[____] += 1             // one more blocker
    
    queue = all courses c where indegree[c] == ____
    taken = 0
    
    while queue is not empty:
        c = queue.popFront()
        taken += 1
        for each nxt in adj[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.push(nxt)
    
    return taken == ____

Hints

[a, b] reads 'b BEFORE a': the arrow LEAVES b and ENTERS a, so the adjacency append is adj[from].append(to). Which course is 'from'?
Whose blocker count just grew? The course being unlocked (a) gains one unmet prerequisite, not b.
Who may start immediately? Only courses with ZERO unmet prerequisites. What indegree value do you seed the queue with?
The queue always ends empty, so that's no verdict. Compare taken against what number to detect a cycle?

Complexity questions

Each course enters the queue at most once, and each arrow is dissolved exactly once. So the total time is…

O(V + E): one visit per course plus one decrement per prerequisite pair. A course only enters the queue at the single moment its indegree hits 0, and each edge's decrement fires once. When its source course is taken. Summing both: O(V + E). The deque never sorts anything; it's plain first-in, first-out.

What dominates the memory?

O(V + E): adjacency lists hold every arrow once, plus O(V) for indegree and the queue. The adjacency lists store each edge exactly once → O(E), while the indegree array and queue each hold at most V entries → O(V). No matrix needed: lists are exactly why sparse prerequisite graphs stay cheap.

The DFS alternative colors nodes white (unvisited), gray (on the current path), black (finished). What does MEETING a gray node during DFS mean?

You found a back edge. You walked into your own ancestry, which is exactly a cycle. Gray means 'still on the recursion stack': an ancestor of where you're standing. An arrow into a gray node loops back into your own path: a back edge, and a back edge IS a cycle. Black nodes are harmless to revisit: they already finished without finding one.

prerequisites = [] with numCourses = 3. What does the algorithm do?

All three indegrees are 0, so all three courses queue immediately; taken reaches 3 → true. No pairs means no arrows, so every indegree stays 0 and the seed line queues ALL courses at once. Three pops later taken == 3 == numCourses → true. With no dependencies, any order works. Take them alphabetically if you like.

Check your understanding of Course Schedule

prerequisites[i] = [a, b]: what does this pair become in the graph?

An arrow b → a: 'b unlocks a'. The arrow points from the prerequisite to the course it unblocks. Read the pair as a sentence: 'to take a, first take b.' Since b happens FIRST, the arrow leaves b and enters a, b unlocks a. Direction is everything in this problem, and flipping this arrow is the single most common bug. (Reversed arrows still give the right true or false here, because a cycle stays a cycle when every arrow is turned around, but the order and the number of courses taken come out wrong. That is why the bug survives this problem and bites in Course Schedule II.)

When is finishing all courses IMPOSSIBLE?

Exactly when the graph contains a CYCLE: a loop of courses each waiting on the next. A long prerequisite chain is fine, you just take it in order, and shared prerequisites are perfectly normal (calculus unlocks many things). The ONLY dealbreaker is a cycle like [[1,0],[0,1]]: every course in the loop waits for another member of the loop, so none of them can ever go first.

What is indegree(course)?

The number of arrows pointing INTO it, its prerequisites not yet satisfied. indegree counts incoming arrows, and each incoming arrow is a prerequisite you haven't taken yet. The magic value is 0: a course with indegree 0 has NOTHING blocking it and is ready to take right now. Those are exactly the courses Kahn's algorithm hunts for.

Kahn's move: what happens the moment you 'take' a course?

It leaves the graph: every dependent's indegree drops by 1, and anyone reaching 0 becomes takeable and joins the queue. Taking a course dissolves its outgoing arrows: one indegree[nxt] -= 1 per dependent. Dependents are NOT taken instantly; they only become takeable when their LAST blocker disappears, i.e. when their indegree hits exactly 0. That is the moment, and the only moment, they enter the queue.

The queue has drained and the loop is over. How do we know the final answer?

Count processed courses: taken == numCourses → true; fewer → the leftovers are locked in a cycle → false. The queue ALWAYS ends empty: that alone tells you nothing. The real signal is the headcount: every processed course genuinely became unblocked at some point. If taken == numCourses, everyone got unblocked, so no cycle exists. If even one course never reached indegree 0, it is trapped in a cycle with the other survivors, return false.