Course Schedule | Leetcode 207

Welcome to our deep dive on Course Schedule (Leetcode 207). This problem is the quintessential introduction to Topological Sorting and Directed Acyclic Graphs (DAGs).

Problem Statement

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.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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

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

Example 2: numCourses = 2, prerequisites = [[1,0],[0,1]] => Output: false (Explanation: To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. This is a cycle!)

Approach 1: Topological Sort (Kahn's Algorithm - BFS) O(V + E)

If we view courses as "nodes" in a graph, and prerequisites as "directed edges" point from the prerequisite to the target course: 0 -> 1 means 0 must be taken before 1.

We can solve this iteratively using Indegrees. The indegree of a node is the number of edges pointing into it (i.e., how many prerequisites it currently has).

1. Any course with an indegree of 0 has no prerequisites! We can take it immediately.
2. We place all indegree == 0 courses into a Queue.
3. While the Queue is not empty, we "take" the course (pop it). We then look at all the courses that depended on it, and decrement their indegree by 1.
4. If any neighboring course's indegree drops to 0, we add it to the Queue!
5. If we manage to successfully process all numCourses, we return true. If some courses are left with indegrees > 0, a cycle exists, and we return false.

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        adj = [[] for _ in range(numCourses)]
        
        # Build the Adjacency List and Indegree Array
        for course, pre in prerequisites:
            adj[pre].append(course)
            indegree[course] += 1
            
        # Add all courses with 0 prerequisites to the queue
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        
        completed_courses = 0
        
        while queue:
            curr = queue.popleft()
            completed_courses += 1
            
            for neighbor in adj[curr]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
                    
        return completed_courses == numCourses

Complexity Analysis

Approach 2: DFS Cycle Detection O(V + E)

Alternatively, we can use standard Depth-First Search to detect cycles in a directed graph. We traverse down the prerequisite chain recursively. We mark nodes with three states:

• 0: Unvisited
• 1: Visiting (currently in our recursive call stack)
• 2: Fully completely visited (we verified no cycle exists from this node)

If we ever DFS into a node that is currently marked strictly as 1 (Visiting), we have detected a loop!

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            adj[pre].append(course)
            
        # 0 = unvisited, 1 = visiting, 2 = visited
        state = [0] * numCourses
        
        def has_cycle(node):
            if state[node] == 1:
                return True
            if state[node] == 2:
                return False
                
            state[node] = 1 # Mark as visiting
            for neighbor in adj[node]:
                if has_cycle(neighbor):
                    return True
                    
            state[node] = 2 # Mark as fully processed
            return False
            
        for i in range(numCourses):
            if has_cycle(i):
                return False
                
        return True

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (207)