LeetCode #207 Medium

Course Schedule

Given numCourses and a list of prerequisite pairs [a, b] meaning course b must be taken before a, return whether all courses can be finished.

graphstopological-sortbfscycle-detection

Open on LeetCode ↗

02

Intuition

💡

The first job is recognising this as a graph problem at all. Draw an edge b -> a for each pair [a, b] and the question becomes structural: you can finish everything exactly when the graph has no cycle, because a cycle is a set of courses each waiting on another with no valid starting point. Kahn's algorithm answers this without a separate cycle check — repeatedly take any course with no unmet prerequisites, and if the process stalls before all courses are taken, the leftovers are the cycle.

03

Approach

1

Build the graph and get the edge direction right

The pair [a, b] means 'to take a, first take b'. So the dependency flows b -> a: finishing b unlocks a. Reversing this is the most common error and produces a graph whose cycles happen to coincide, so it passes some tests while being conceptually backwards. Alongside the adjacency list, count the in-degree of each course: how many prerequisites it still has unmet.

2

Start from courses with no prerequisites

A course is takeable exactly when its in-degree is zero. Seed a queue with every such course. If no course has in-degree zero at the start, every course waits on another and the answer is immediately false — that stall is already the cycle showing itself.

3

Peel off takeable courses and watch for a stall

Pop a course, mark it taken, and decrement the in-degree of everything it unlocks. Any course whose count reaches zero joins the queue. Continue until the queue empties, then compare the number taken against numCourses. Equal means every course was reachable and no cycle exists. Fewer means the remainder are locked in a cycle where each waits on another and no in-degree ever falls to zero. O(V + E) — each edge is decremented exactly once, and no explicit cycle detection is written anywhere.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3class Solution:
▶4    def canFinish(self, numCourses, prerequisites):
▶5        adj = [[] for _ in range(numCourses)]
▶6        indeg = [0] * numCourses
▶7        for a, b in prerequisites:
▶8            adj[b].append(a)
▶9            indeg[a] += 1
▶10        q = deque(i for i in range(numCourses) if indeg[i] == 0)
▶11        taken = 0
▶12        while q:
▶13            c = q.popleft()
▶14            taken += 1
▶15            for nxt in adj[c]:
▶16                indeg[nxt] -= 1
▶17                if indeg[nxt] == 0:
▶18                    q.append(nxt)
▶19        return taken == numCourses

05

Edge cases

No prerequisites at all

Every course starts at in-degree 0, all are queued immediately, and the answer is true.

A self-loop, e.g. [1, 1]

Course 1 has in-degree 1 that nothing can decrement, so it never becomes takeable and the count falls short — correctly false.

Disconnected components

Kahn's seeds from every in-degree-0 vertex, so independent groups are processed in parallel with no special handling.

Duplicate prerequisite pairs

Each duplicate raises the in-degree and is decremented once, so the counts stay balanced and the result is unaffected.

06

Complexity

Time

O(V + E)

Space

O(V + E)

Every vertex is queued at most once and every edge decremented exactly once. The space is the adjacency list plus the in-degree array.