# Course Schedule

- **Canonical ID**: `course-schedule`
- **Canonical URL**: https://dsacheatsheet.com/problems/course-schedule
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/course-schedule/

## 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

- **Time Complexity**: `O(V + E)`
- **Space Complexity**: `O(V + E)`
- **Proof**: Every vertex enters the queue at most once and every directed edge reduces its target indegree once.

## 3. Minimal Idiomatic Code

### Python
```python
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
```

### TypeScript
```typescript
export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg = new Int32Array(numCourses);
  for (const [a, b] of prerequisites) {
    adj[b].push(a);
    indeg[a]++;
  }
  const q: number[] = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  for (let head = 0; head < q.length; head++) {
    taken++;
    for (const v of adj[q[head]]) {
      if (--indeg[v] === 0) q.push(v);
    }
  }
  return taken === numCourses;
}
```

### C++
```cpp
bool canFinish(int n, vector<vector<int>>& prereqs) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n);
    for (auto& p : prereqs) { adj[p[1]].push_back(p[0]); indeg[p[0]]++; }
    queue<int> q;
    for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
    int taken = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); taken++;
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    return taken == n;
}
```

### Java
```java
boolean canFinish(int n, int[][] prereqs) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] p : prereqs) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
    Queue<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int taken = 0;
    while (!q.isEmpty()) {
        int u = q.poll(); taken++;
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return taken == n;
}
```

### Go
```go
func canFinish(n int, prereqs [][]int) bool {
    adj := make([][]int, n)
    indeg := make([]int, n)
    for _, p := range prereqs { adj[p[1]] = append(adj[p[1]], p[0]); indeg[p[0]]++ }
    var q []int
    for i, d := range indeg { if d == 0 { q = append(q, i) } }
    taken := 0
    for len(q) > 0 {
        u := q[0]; q = q[1:]; taken++
        for _, v := range adj[u] {
            indeg[v]--
            if indeg[v] == 0 { q = append(q, v) }
        }
    }
    return taken == n
}
```

## 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.