Course Schedule

Difficulty: Medium Source: NeetCode

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return true if you can finish all courses. Otherwise, return false.

Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true

Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• All prerequisite pairs are unique
• No self-loops

Prerequisites

Before attempting this problem, you should be comfortable with:

• Directed graphs — modeling courses as nodes and prerequisites as directed edges
• Cycle detection in directed graphs — the core problem reduces to this
• Topological sort — a valid ordering only exists if no cycle is present

1. DFS with Three-Color Cycle Detection

Intuition

Build a directed graph from prerequisites (edge from b to a means “take b before a”). The courses can be completed if and only if this graph has no cycle. DFS can detect cycles using three states: WHITE (unvisited), GRAY (currently in the DFS stack — part of the current path), and BLACK (fully processed). If DFS reaches a GRAY node, we’ve found a cycle.

Algorithm

1. Build adjacency list from prerequisites.
2. Mark all nodes as WHITE (0).
3. For each unvisited node, run DFS:
   • Mark it GRAY (1) when entering.
   • For each neighbor: if GRAY, cycle found — return False; if WHITE, recurse.
   • Mark it BLACK (2) when done.
4. Return True if no cycle found.

Solution

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        graph[b].append(a)  # b must come before a

    # 0 = unvisited, 1 = in-stack (GRAY), 2 = done (BLACK)
    state = [0] * numCourses

    def dfs(node):
        if state[node] == 1:  # cycle detected
            return False
        if state[node] == 2:  # already processed, safe
            return True
        state[node] = 1       # mark as in-stack
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2       # mark as done
        return True

    for course in range(numCourses):
        if not dfs(course):
            return False
    return True


print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]]))  # False
print(canFinish(5, [[1,0],[2,1],[3,2],[4,3]]))  # True (chain, no cycle)
print(canFinish(3, [[1,0],[2,1],[0,2]]))         # False (cycle)

Complexity

• Time: O(V + E) where V = numCourses, E = len(prerequisites)
• Space: O(V + E) for graph and recursion stack

2. Topological Sort (Kahn’s BFS Algorithm)

Intuition

A directed graph is acyclic (a DAG) if and only if it has a valid topological ordering. Kahn’s algorithm builds this ordering using in-degrees: repeatedly pick nodes with in-degree 0 (no remaining prerequisites), remove them, and decrement their neighbors’ in-degrees. If we can process all numCourses nodes this way, no cycle exists. If the queue empties before processing all nodes, there’s a cycle.

Algorithm

1. Compute in-degree for each node.
2. Enqueue all nodes with in-degree 0.
3. While queue is non-empty: dequeue a node, increment processed count, decrement neighbors’ in-degrees. Enqueue neighbors that reach in-degree 0.
4. Return processed == numCourses.

Solution

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1

    queue = deque(course for course in range(numCourses) if in_degree[course] == 0)
    processed = 0

    while queue:
        course = queue.popleft()
        processed += 1
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return processed == numCourses


print(canFinish(2, [[1,0]]))        # True
print(canFinish(2, [[1,0],[0,1]]))  # False
print(canFinish(1, []))             # True
print(canFinish(3, [[1,0],[2,1],[0,2]]))  # False

Complexity

• Time: O(V + E)
• Space: O(V + E)

Common Pitfalls

Edge direction. prerequisites[i] = [a, b] means b → a (take b first). When building the adjacency list, make sure you add an edge from b to a, not the other way around.

Rerunning DFS on already-processed nodes. If state[node] == 2 (BLACK), the node was already confirmed cycle-free — return True immediately without processing it again. Skipping this check causes redundant work and potential stack overflows.

Kahn’s: missing isolated nodes. Nodes with no prerequisites start with in-degree 0 and must be seeded into the initial queue. If you forget them, processed won’t reach numCourses even when no cycle exists.