Skip to main content

🟨 Course Schedule (#207)

🔗 Problem Link​

📋 Problem Statement​

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. 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.

🔑 Key Insights & Approach​

Core Observation: Detect cycle in directed graph using DFS with states or topological sort.

Pattern: "Cycle Detection in Directed Graph" using DFS.

🐍 Solution: Python​

from typing import List
from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for course, prereq in prerequisites:
            graph[course].append(prereq)
        
        visiting = set()
        visited = set()
        
        def dfs(course):
            if course in visiting:
                return False
            if course in visited:
                return True
            
            visiting.add(course)
            for prereq in graph[course]:
                if not dfs(prereq):
                    return False
            
            visiting.remove(course)
            visited.add(course)
            return True
        
        for course in range(numCourses):
            if not dfs(course):
                return False
        
        return True

📚 References​