Course Schedule — InterviewPrepKit

Solving tips

Reframe as cycle detection on a directed graph: prerequisite [a,b] means edge b -> a ('b unlocks a'), and all courses are finishable iff the graph is acyclic.
Kahn's algorithm (BFS): compute in-degrees, queue the in-degree-0 courses, and decrement dependents as you take each; if the count taken equals numCourses there is no cycle.
DFS alternative uses three colors (white/gray/black) — reaching a GRAY node is a back edge (cycle); a plain visited set can't distinguish 'on stack' from 'finished' and misreports.
Both are O(V+E); watch the edge direction and note the long-chain (up to 2000) recursion-limit risk favors Kahn's.

Problem

There are numCourses courses labeled 0 to numCourses - 1. You’re given a list prerequisites where each entry [a, b] means “to take course a, you must first finish course b.”

Return True if it’s possible to finish every course, and False otherwise.

Finishing all courses is possible exactly when the prerequisite relation contains no circular dependency (you can’t have a needing b needing … needing a).

Examples

numCourses = 2, prerequisites = [[1,0]] → True — take 0, then 1.
numCourses = 2, prerequisites = [[1,0],[0,1]] → False — 1 needs 0 and 0 needs 1, a cycle.
numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → True — order 0, 1, 2, 3 works (0, 2, 1, 3 works too).

Constraints

1 <= numCourses <= 2000
0 <= len(prerequisites) <= 5000
Each prerequisites[i] is a pair of distinct course labels; no duplicate pairs.

Think about it first

Hint 1

Model courses as nodes and each prerequisite [a, b] as a directed edge b → a ("b unlocks a"). The question "can I finish everything?" becomes "does this directed graph have a cycle?"

Hint 2

Two classic cycle tests for a directed graph. (1) DFS with three states — unvisited / in the current recursion stack / fully done — where revisiting a node that's still on the stack is a back edge, i.e. a cycle. (2) Kahn's algorithm: repeatedly remove a node with no remaining prerequisites; if you can't remove all of them, the leftovers form a cycle.

Hint 3

For Kahn's: compute each course's in-degree (how many prerequisites it still has), start a queue with the in-degree-0 courses, and each time you "take" a course, decrement its dependents' in-degrees, enqueueing any that hit 0. If the number of courses taken equals numCourses, there's no cycle.

TL;DR

Build the prerequisite graph and detect a cycle — Kahn’s BFS topological sort or DFS three-coloring, both O(V + E) time and space.

Approach 1 — Brute force (repeatedly strip courses you can take)

The naive intuition: scan the list, take any course whose prerequisites are all already taken, mark it done, and repeat the whole scan until nothing changes. If everything gets taken, return True.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        taken = [False] * numCourses
        remaining = numCourses
        while True:
            progressed = False
            for course in range(numCourses):
                if taken[course]:
                    continue
                if all(taken[b] for a, b in prerequisites if a == course):
                    taken[course] = True
                    remaining -= 1
                    progressed = True
            if not progressed:
                return remaining == 0

Complexity: each outer pass rescans every prerequisite, and you may need up to numCourses passes → O(V · E). With V = 2000 and E = 5000 that’s ten million checks per stall — this is exactly Kahn’s algorithm done inefficiently, so let’s do it properly.

Approach 2 — Kahn’s algorithm (BFS topological sort)

The insight: a course with in-degree 0 has no unmet prerequisites, so you can take it now. Taking it removes it as a prerequisite for its dependents, lowering their in-degrees. Keep a queue of the currently-takeable courses. If you manage to take all numCourses, the graph is acyclic; if the queue empties early, whatever’s left is stuck in a cycle. Kahn’s algorithm is exactly this in-degree peeling.

from collections import deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for a, b in prerequisites:      # b must come before a: edge b -> a
            adj[b].append(a)
            indegree[a] += 1

        queue = deque(c for c in range(numCourses) if indegree[c] == 0)
        taken = 0
        while queue:
            course = queue.popleft()
            taken += 1
            for nxt in adj[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return taken == numCourses

Walkthrough (numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]):

Edges: 0→1, 0→2, 1→3, 2→3. In-degrees: 0:0, 1:1, 2:1, 3:2. Queue [0].
Take 0 (taken=1); decrement 1→0 and 2→0, enqueue both. Queue [1,2].
Take 1 (taken=2); 3 drops to 1. Take 2 (taken=3); 3 drops to 0, enqueue. Take 3 (taken=4).
taken == 4 == numCourses → True.

On the cyclic [[1,0],[0,1]], both courses start at in-degree 1, the queue is empty from the start, taken stays 0 → False.

Complexity: building the graph is O(E); each node and edge is processed once → O(V + E) time, O(V + E) space.

Approach 3 — DFS three-color cycle detection

The insight: run DFS and track each node’s state — WHITE (unseen), GRAY (on the current recursion stack), BLACK (fully explored). Reaching a GRAY node means a back edge, which is precisely a cycle. Nodes marked BLACK are known-safe and never re-explored, keeping it linear. DFS is preferred when you also want the recursion structure (e.g. to detect which cycle); Kahn’s is preferred when you’d rather avoid recursion limits and get a valid order as a byproduct.

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            adj[b].append(a)

        WHITE, GRAY, BLACK = 0, 1, 2
        state = [WHITE] * numCourses

        def has_cycle(course: int) -> bool:
            state[course] = GRAY
            for nxt in adj[course]:
                if state[nxt] == GRAY:
                    return True                 # back edge → cycle
                if state[nxt] == WHITE and has_cycle(nxt):
                    return True
            state[course] = BLACK
            return False

        return not any(
            state[c] == WHITE and has_cycle(c) for c in range(numCourses)
        )

Walkthrough ([[1,0],[0,1]] → edges 0→1, 1→0): DFS from 0 marks 0 GRAY, visits 1, marks 1 GRAY, follows 1→0 and finds 0 is GRAY → cycle → returns True, so canFinish returns False.

Complexity: each node turns GRAY then BLACK once and each edge is examined once → O(V + E) time, O(V + E) space (graph + recursion stack).

Common pitfalls

Reversing the edge direction. [a, b] means “b before a,” so the edge is b → a; getting this backwards inverts the whole answer only in asymmetric graphs but silently passes symmetric tests.
Using a plain visited set instead of three colors in DFS: you can’t distinguish “still on the stack” (cycle) from “finished on another branch” (fine), producing false cycle reports.
Forgetting isolated courses with no prerequisites — they start at in-degree 0 and must be counted as takeable.
Hitting Python’s recursion limit on a long dependency chain (up to 2000 deep) with the DFS version; Kahn’s has no such issue.

Pattern takeaway

“Can all tasks with dependencies be completed?” is cycle detection on a directed graph. Reach for topological sorting: Kahn’s in-degree BFS returns feasibility (and an order) with no recursion, while DFS three-coloring detects the back edge directly. Both are O(V + E) — choose by whether you want an ordering or explicit stack structure.