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

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)

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.

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.

Related problems

Keep practising