Course Schedule

MediumAmazonGoogleMetaMicrosoft

Problem

There are numCourses courses (0 to numCourses-1). prerequisites[i] = [a, b] means must take b before a. Return true if you can finish all courses.

Intuition — the key insight

This is cycle detection in a directed graph. If there's a cycle, some course depends on itself (directly or indirectly) — impossible. Use DFS with three states: unvisited, in-progress (on current path), visited (fully processed).

Approach

DFS with states

Build adjacency list. For each unvisited node, DFS. Mark as in-progress. If we reach an in-progress node, cycle found → return false. After processing all neighbors, mark as fully visited.

Complexity

Time

O(V+E)

Space

O(V+E)

Visit each node and edge once. Adjacency list + state array.

Solution code

Python

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    for a,b in prerequisites:
        graph[b].append(a)
    
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    
    def dfs(node):
        if state[node] == 1: return False  # cycle!
        if state[node] == 2: return True
        state[node] = 1
        for nei in graph[node]:
            if not dfs(nei): return False
        state[node] = 2
        return True
    
    return all(dfs(i) for i in range(numCourses) if state[i]==0)

Edge cases to remember

⚠No prerequisites: always true

⚠Self-loop [[0,0]]: cycle, return false

⚠Disconnected graph: iterate all nodes

Hints

What pattern do you think this problem uses?