LeetCode Study Note | Problem 207: Course Schedule

Problem Summary

You are given numCourses courses labeled from 0 to numCourses - 1, and a list of prerequisites where each element is a pair [a, b] meaning to take course a, you must first take course b.

Goal: Determine if you can finish all courses (i.e., no circular dependency exists).

Example

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: True  # You can take course 0 first, then course 1

Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: False  # Circular dependency exists

Key Insight

This is essentially a cycle detection problem in a directed graph.

If there is a cycle, the courses cannot be completed.

Solution 1: Topological Sort using BFS (Kahn’s Algorithm)

Steps:

1. Build a graph using an adjacency list.

2. Count the in-degrees of all nodes.

3. Add all nodes with in-degree 0 to a queue.

4. Repeatedly remove nodes from the queue and reduce the in-degree of their neighbors.

5. If all nodes are visited, return True; otherwise, a cycle exists.

Code:

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    in_degree = [0] * numCourses
    graph = defaultdict(list)

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

    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    visited = 0

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

    return visited == numCourses

Time Complexity:

• O(V + E): where V is number of courses, E is number of prerequisites

Space Complexity:

• O(V + E): for graph and in-degree tracking

Solution 2: DFS with Cycle Detection

Steps:

1. Build a graph using an adjacency list.

2. Use a visited array to track states:

   • 0: unvisited

   • 1: visiting (in recursion stack)

   • 2: visited

3. If you visit a node that is already “visiting”, a cycle exists.

Code:

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for dest, src in prerequisites:
        graph[src].append(dest)

    visited = [0] * numCourses

    def dfs(node):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True

        visited[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 2
        return True

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

Time Complexity:

• O(V + E)

Space Complexity:

• O(V + E) for the graph, plus O(V) recursion stack in the worst case

Conclusion

• This problem is a classic application of topological sorting.

• Choose:

  • BFS (Kahn’s Algorithm) if you prefer an iterative solution.

  • DFS if you’re comfortable with recursion and state tracking.

• Mastering this pattern helps with many course scheduling, build system, and dependency resolution problems.