NeetCode #576LC-210MediumGraphsNC 150NC 250
← Back to All Problems#576 · #210 · Course Schedule II(课程表 II)
📌 Problem Statement & Constraints
There are
numCourses courses and prerequisites[i] = [a, b] means b before a. Return a valid order to finish all courses, or an empty array if impossible. Constraints: 1 <= numCourses <= 2000, 0 <= prerequisites.length <= numCourses * (numCourses - 1).💡 Core Algorithmic Approaches
- This is a topological sort. Kahn's algorithm produces the order directly.
- Start from all in-degree-zero nodes; each removal appends to the order and decrements its successors' in-degrees.
- If the order contains all nodes, it is valid; otherwise a cycle exists and the answer is empty.
- Any valid topological order is accepted, so the tie-breaking does not matter.
💻 Benchmark Python3 Implementation
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
from collections import defaultdict, deque
g = defaultdict(list)
indeg = [0] * numCourses
for a, b in prerequisites: # b must precede a
g[b].append(a)
indeg[a] += 1
q = deque(i for i in range(numCourses) if indeg[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nxt in g[node]:
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return order if len(order) == numCourses else []⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph.
⚠️ Interview Pitfalls & Follow-ups
- Returning a partial order when a cycle exists: the length check converts it to an empty array.
- Appending to the order when enqueuing instead of when popping: the ordering constraint would be violated.
- Reversing the edge direction:
[a, b]meansb -> a. - Sorting the output: any valid order is accepted, and sorting could break the constraints.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.