Course Schedule II
mediumTests passed 2026-11-11v1.0.01. Core Invariant / The Trick
Same Kahn’s topological sort as Course Schedule, collecting each dequeued vertex into `order`. Return `order` iff `len(order) == numCourses`, else `[]`.
2. Complexity Bounds & Proof
Queue pushes vertices only when all prerequisites are satisfied; linear pass emits a valid total order or detects a cycle via shortfall.
3. Minimal Idiomatic Code
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
adj = [[] for _ in range(numCourses)]
indeg = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
indeg[a] += 1
q = deque(i for i, d in enumerate(indeg) if d == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == numCourses else []4. Failure Modes & Interview Follow-ups
Pitfalls:- Returning partial `order` instead of `[]` when a cycle prevents completing all courses.
Follow-ups:- Lexicographically smallest topological sort: replace the FIFO queue with a min-heap (`heapq`).
Personal Notes & Scratchpad (Local-First Yjs CRDT)
Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.
Related Invariants
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.