LeetEye LeetEye
Medium Graph Traversal ~5 min

Course Schedule

graphs course-schedule

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.

Examples

Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Take course 0 first, then course 1.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Circular dependency. Can't finish either.
Key Insight

If there's a cycle in prerequisites, you can't finish. No cycle = can finish.

Cycle in directed graph = can't finish. DFS with 3 states (unvisited/visiting/visited): if we reach a 'visiting' node, cycle found. Or use Kahn's: if completed < numCourses, cycle exists.

How to Approach This Problem

Pattern Recognition: When you see keywords like course schedule graphs, think Graph Traversal.

Step-by-Step Reasoning

1 prerequisites = [[1,0], [2,1]] means:
Answer: Both B and C
[a,b] means b must come before a. Edge from b to a, or "b→a".
2 A cycle in prerequisites means:
Answer: Some courses form a circular dependency
A→B→C→A means you can't start any of them.
3 To detect cycles in directed graph:
Answer: DFS with visited states
DFS with "visiting" (in current path) and "visited" (fully processed) states.
4 In cycle detection DFS, each node can be:
Answer: Unvisited, visiting, visited (3 states)
Unvisited = not seen. Visiting = in current DFS path. Visited = fully processed.
5 A cycle exists if during DFS we reach:
Answer: A "visiting" node
Reaching a node that's currently in our path = we've found a back edge = cycle.
6 Using Kahn's algorithm (BFS topological sort):
Answer: If queue empties before all nodes processed, there's a cycle
Kahn's removes nodes with 0 in-degree. If cycle exists, some nodes never reach 0 in-degree.

Solution

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # Build adjacency list
    graph = {i: [] for i in range(numCourses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    # 0 = unvisited, 1 = visiting, 2 = visited
    state = [0] * numCourses
    
    def dfs(course):
        if state[course] == 1:  # Cycle detected
            return False
        if state[course] == 2:  # Already processed
            return True
        
        state[course] = 1  # Mark visiting
        
        for prereq in graph[course]:
            if not dfs(prereq):
                return False
        
        state[course] = 2  # Mark visited
        return True
    
    for course in range(numCourses):
        if not dfs(course):
            return False
    
    return True

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye