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 ().prerequisites: List of directed edges .
Outputs:
- Boolean:
Trueif all courses can be finished (DAG),Falseotherwise.
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 () require an 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 , which will Time Out immediately for numCourses as small as 20 and definitely fails at .
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:
- Model the courses as nodes and dependencies as edges in an adjacency list.
- Track how many prerequisites each course has remaining (
in-degree). - 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
- 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. - Initialization: Identify all “root” nodes—courses with no prerequisites (0 in-degree). Add these to a queue/stack initially.
- 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-degreebecause 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.
- 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: , where is the number of courses and 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: . The adjacency list stores every edge, we store an array for
in-degreeof size 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
indegreearray remains all zeros. All nodes are added to the queue initially; loop runs times; returnsTrue. - 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_countwill fall short ofnumCourses, returningFalse. - Large Inputs (): Using an iterative BFS approach avoids Python recursion limits (
sys.setrecursionlimit) and ensures memory usage scales linearly with input size rather than stack depth.