Domain 2MediumCORE

Course Schedule

We are given numCourses, representing nodes in a graph labeled 0 through numCourses - 1. The input is an array of prerequisites, where each pair [ai, bi] signifies that course bi must be completed before taking course ai. This defines a directed edge from node bi to node ai.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search#Graph#Topological Sort

207. Course Schedule

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Graph,Topological Sort
FAANG asked: 1
Acceptance rate: 44.3%


Problem Breakdown

We are given numCourses, representing nodes in a graph labeled 0 through numCourses - 1. The input is an array of prerequisites, where each pair [a_i, b_i] signifies that course b_i must be completed before taking course a_i. This defines a directed edge from node b_i to node a_i.

The core question asks if it’s possible to complete all courses. In graph theory terms, this is equivalent to determining whether the dependency graph contains any cycles. If there is a cycle (e.g., A requires B, and B requires A), we can never satisfy both conditions simultaneously. Therefore, the problem reduces to Cycle Detection in a Directed Graph.

Inputs:

  • numCourses: Integer count of nodes (VV).
  • prerequisites: List of directed edges EE.

Outputs:

  • Boolean: True if all courses can be finished (DAG), False otherwise.

Edge Cases & Constraints:

  • Empty prerequisites list implies no dependencies, so it should return true.
  • Disconnected components are possible; the algorithm must handle nodes with zero in-degree that aren’t connected to others.
  • Large inputs (N=105N=10^5) require an O(V+E)O(V+E) solution rather than recursion-heavy DFS without stack limit adjustments or brute force permutations.

Intuition

A naive approach might be trying every possible ordering of courses (permutations). However, checking all orderings is factorial time complexity O(N!)O(N!), which will Time Out immediately for numCourses as small as 20 and definitely fails at 10510^5.

The problem describes dependencies. If we can find a valid linear ordering where every course appears after its prerequisites, the schedule exists. This is exactly what Topological Sort solves. A directed graph admits a topological sort if and only if it contains no cycles (it is a Directed Acyclic Graph or DAG).

Therefore, our strategy should be:

  1. Model the courses as nodes and dependencies as edges in an adjacency list.
  2. Track how many prerequisites each course has remaining (in-degree).
  3. Process courses that have zero pending prerequisites first (BFS/Kahn’s Algorithm) or use DFS to detect back-edges indicating cycles.

I will proceed with Kahn’s Algorithm (BFS-based Topological Sort) because it avoids recursion depth issues common in Python for large inputs and is very explicit about the “progress” of completing courses.

Approach

  1. Graph Construction: Create an adjacency list where adj[prereq] contains all courses that depend on it. Simultaneously, maintain an array to track the number of incoming edges (in-degree) for each course.
  2. Initialization: Identify all “root” nodes—courses with no prerequisites (0 in-degree). Add these to a queue/stack initially.
  3. Processing Loop: While there are courses left to process:
    • Pop a course from the queue. Increment our count of completed courses.
    • For every dependent course, decrement its in-degree because we have just “completed” one prerequisite for it.
    • If any dependent course now has 0 in-degrees (all prerequisites met), add it to the queue.
  4. Validation: After processing all reachable nodes from zero-indegree sources, compare our count of completed courses against numCourses. If they match, we finished everything; otherwise, a cycle blocked some courses.

Complexity Analysis

  • Time Complexity: O(V+E)O(V + E), where VV is the number of courses and EE is the length of prerequisites. We iterate through each node once to initialize in-degrees and edges exactly once during graph traversal. Building the adjacency list takes linear time relative to input size.
  • Space Complexity: O(V+E)O(V + E). The adjacency list stores every edge, we store an array for in-degree of size VV plus a queue that can hold at most all nodes in worst case (though typically much less).

Solution

from collections import deque

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # Build adjacency list and in-degree count array
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    
    for course, prereq in prerequisites:
        # Edge direction is from prerequisite -> dependent course
        adj[prereq].append(course)
        indegree[course] += 1
        
    # Initialize queue with all courses having no dependencies (in-degree == 0)
    queue = deque([i for i, count in enumerate(indegree) if count == 0])
    
    completed_count = 0
    
    while queue:
        current_course = queue.popleft()
        completed_count += 1
        
        # Iterate over courses that depend on the current course being finished
        for dependent_course in adj[current_course]:
            indegree[dependent_course] -= 1
            
            # If all prerequisites are met, add to processing queue
            if indegree[dependent_course] == 0:
                queue.append(dependent_course)
                
    return completed_count == numCourses

Edge Cases Handled

  • No Prerequisites: The indegree array remains all zeros. All nodes are added to the queue initially; loop runs NN times; returns True.
  • Disconnected Graphs: Nodes with no incoming edges from other components will naturally be picked up by the initial zero-in-degree check, ensuring isolated courses don’t cause false negatives.
  • Cycle Detection: If a cycle exists (e.g., A->B and B->A), neither node’s in-degree ever drops to 0 after processing their neighbors. The completed_count will fall short of numCourses, returning False.
  • Large Inputs (10510^5): Using an iterative BFS approach avoids Python recursion limits (sys.setrecursionlimit) and ensures memory usage scales linearly with input size rather than stack depth.