210. Course Schedule II
Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Graph,Topological Sort
FAANG asked: 1
Acceptance rate: 42.9%
Problem Breakdown
We are given numCourses and a list of prerequisite pairs [a, b], where taking course b is required before taking course a. This defines a directed graph where an edge exists from b -> a. The goal is to find a linear ordering (topological sort) such that for every pair (u, v) in the prerequisites list, node v appears before node u in our output. If no such valid order exists—specifically if there is a cycle—we must return an empty array.
Inputs:
numCourses: Integer (1 to 2000).prerequisites: List of pairs[a, b].
Outputs:
- A list representing the course ordering.
- Empty list
[]if a cycle exists or courses cannot be completed.
Implicit Constraints & Edge Cases:
- Cycles: If there is a circular dependency (e.g., 0 needs 1, and 1 needs 0), it’s impossible to finish all courses.
- Disconnected Components: Some courses might have no prerequisites at all; they should be included in the order naturally.
- Single Course: Valid even with empty prerequisite list.
Intuition
A naive approach would try every possible permutation of course orders and check validity, which is —far too slow for numCourses up to 2000. We need a more efficient way to respect dependencies.
The core insight here is that this problem maps directly to Topological Sorting. If we view courses as nodes in a directed graph and prerequisites as edges, the solution exists if and only if the graph contains no cycles (i.e., it’s a Directed Acyclic Graph or DAG).
To find an ordering:
- We must process any course that has no pending dependencies first. In graph terms, these are nodes with an in-degree of 0.
- Once we “take” such a course, its dependent courses lose one prerequisite requirement (their in-degree decreases by 1). If a dependent course’s prerequisites drop to zero, it becomes available for processing next.
This suggests a Breadth-First Search (BFS) approach using Kahn’s Algorithm rather than Depth-First Search (DFS), as BFS naturally handles the “available now” logic via a queue and makes cycle detection explicit by checking if we processed all nodes.
Approach
- Graph Construction: Build an adjacency list to represent the graph where
adj[b]contains neighbors[a]. Simultaneously, calculate the in-degree (number of prerequisites) for every course. - Initialization: Create a queue and add all courses with an initial in-degree of 0 into it. These are our starting points.
- Processing Loop: While the queue is not empty:
- Dequeue a node
u. Adduto our result list (this represents taking courseu). - For every neighbor
vconnected fromu:- Decrement
in_degree[v]. - If
in_degree[v] == 0, enqueuev.
- Decrement
- Dequeue a node
- Cycle Check: After the loop, compare the length of our result list to
numCourses. If they match, we found a valid topological order. If not (result is shorter), it means some nodes were never reachable because they are part of a cycle; return an empty array in that case.
Complexity Analysis
- Time: where is
numCoursesand is the number of prerequisites. We iterate through each node once to initialize, then visit every edge exactly once during processing. Given constraints (), this fits well within time limits. - Space: required for storing the adjacency list and in-degree array. The queue uses at most .
Solution
from collections import deque, defaultdict
def findOrder(numCourses: int, prerequisites):
# Build graph (adjacency list) and calculate in-degrees
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for course_a, prereq_b in prerequisites:
# Edge from prerequisite to dependent course
adj[prereq_b].append(course_a)
in_degree[course_a] += 1
queue = deque()
# Initialize with all courses having no prerequisites (in-degree == 0)
for i in range(numCourses):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
u = queue.popleft()
result.append(u)
# Visit neighbors (courses that depend on current course 'u')
for v in adj[u]:
in_degree[v] -= 1
# If all prerequisites are met, add to queue
if in_degree[v] == 0:
queue.append(v)
# Check if we were able to order all courses (no cycle detected)
return result if len(result) == numCourses else []
# Example usage for verification
print(findOrder(2, [[1,0]])) # Output: [0, 1]
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])) # Output: [0, 1, 2, 3] or similar valid order
Edge Cases Handled
- No Prerequisites: All nodes start with in-degree 0. The queue processes them sequentially (order arbitrary but valid). Returns
[0, 1, ..., n-1]. - Cycle Detected: If a cycle exists, the loop terminates before all
numCoursesare added toresult. We checklen(result) == numCoursesand return empty list if false. - Disconnected Graphs: Courses with no edges (isolated nodes) have in-degree 0 initially and get processed immediately alongside others, ensuring they appear in the output correctly without affecting dependency logic for other components.