Course Schedule (LeetCode 207)

The problem

There are n courses labelled 0 to n - 1. Each pair [a, b] in prereqs means “you must take b before a”. Return True if it’s possible to finish every course, and False otherwise.

Input:  n = 2, prereqs = [[1, 0]]
Output: True

Input:  n = 2, prereqs = [[1, 0], [0, 1]]
Output: False

In the first case, take 0, then 1. In the second, each course needs the other first, so neither can ever start.

How to think about it

Start with brute force. Try every ordering of the n courses and check whether each one respects all prerequisites. That’s n! orderings, which is already impossible at n = 15.

The key insight: this is a directed graph, and the answer is “no” exactly when it has a cycle. Draw an edge b → a for each prerequisite. If the graph has no cycle, you can always find a valid order (a topological order). If it has a cycle, the courses on it wait on each other forever. So the real question is “is this directed graph acyclic?”

How to find an order, or prove there isn’t one: peel off the free courses. A course with in-degree 0 has no unmet prerequisites, so you can take it now. Take it, and remove its outgoing edges: that lowers the in-degree of the courses that depended on it, and some of them may become free. Repeat. This is Kahn’s algorithm. If you manage to take all n courses, there’s no cycle. If the queue empties early, the courses left over are stuck on a cycle.

Which pattern is this? Topological sort. The tell is “tasks with dependencies: can they all be done, or in what order?“. DFS with three colours (unvisited, in progress, done) also detects the cycle, but Kahn’s BFS is easier to get right under pressure.

Approach

1. Build the adjacency list b → a and count indeg[a] for each prerequisite.
2. Put every course with in-degree 0 in a queue.
3. Pop a course, count it as taken (seen += 1), and decrement the in-degree of each course that depends on it. Push any that reach 0.
4. When the queue is empty, return seen == n.

Solution

from collections import defaultdict, deque
def can_finish(n, prereqs):
    adj = defaultdict(list); indeg = [0]*n
    for a, b in prereqs: adj[b].append(a); indeg[a] += 1     # edge b -> a
    q = deque([i for i in range(n) if indeg[i] == 0]); seen = 0   # courses free to take now
    while q:
        u = q.popleft(); seen += 1
        for v in adj[u]:
            indeg[v] -= 1                                     # one prerequisite of v is done
            if indeg[v] == 0: q.append(v)
    return seen == n                                          # anything left is on a cycle
# can_finish(2, [[1,0]]) -> True ;  can_finish(2, [[1,0],[0,1]]) -> False

Dry run

A slightly bigger example with a cycle: n = 4, prereqs = [[1,0],[2,1],[3,2],[1,3]]. The edges are 0 → 1 → 2 → 3 → 1.

Course 1 still waits on course 3, which waits on 2, which waits on 1. The queue is empty with seen = 1 < 4, so the answer is False. On the first example, [[1,0]], the queue goes [0] → [1] → [] and seen reaches 2, so the answer is True.

Complexity

• Time: O(V + E). Each course is pushed and popped once, and each prerequisite edge is relaxed once.
• Space: O(V + E) for the adjacency list, the in-degree array and the queue.

Edge cases and pitfalls

• No prerequisites: every course starts in the queue, the answer is True.
• Self-loop [0, 0]: course 0 has in-degree 1 from itself and never enters the queue, so False. Correct.
• Edge direction. [a, b] means b before a, so the edge is b → a. Reversing it still detects cycles here, but would give a backwards order in Course Schedule II.
• Disconnected courses are handled: every in-degree-0 node starts in the queue, whatever component it’s in.
• Duplicate prerequisite pairs are fine: they add to the in-degree and are subtracted the same number of times.

Related problems

• Course Schedule II (LeetCode 210): the same algorithm, returning the order itself.
• Alien Dictionary (LeetCode 269): build the dependency graph from sorted words, then topologically sort.
• Graph Valid Tree (LeetCode 261): cycle detection on an undirected graph, using union-find.