Course Schedule

mediumTests passed 2026-11-11v1.0.0
TC: O(V + E)|SC: O(V + E)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Kahn’s algorithm: track `indegree[v]` and push all `0`-indegree vertices into a queue. Repeatedly pop `u`, decrement neighbors’ indegrees, enqueue newly zeroed vertices, and verify `visited == numCourses`.

2. Complexity Bounds & Proof

Every vertex enters the queue at most once and every directed edge reduces its target indegree once.

3. Minimal Idiomatic Code

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    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)
    taken = 0
    while q:
        u = q.popleft()
        taken += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return taken == numCourses

4. Failure Modes & Interview Follow-ups

Pitfalls:- Note edge orientation: `[a, b]` means take `b` BEFORE `a` (`b -> a`), so `indegree[a]++`. - Using only a 2-state `visited` set in DFS misses directed cycles; DFS needs 3 states (`unvisited`, `visiting`, `visited`).
Follow-ups:- Returning an actual build/course ordering directly transitions to Course Schedule II.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Course Schedule II (O(V + E))Graph Valid Tree (O(N * a(N)))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.