117 — Course Schedule

117 — Course Schedule

LeetCode 207 · Medium. There are numCourses courses labeled 0 to numCourses - 1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if it's possible to finish all courses.

---

🍽️ Intuition

"Course b before course a" is a directed edge b → a. "Can all courses be finished" is then just "does this directed graph have a valid ordering at all" — and a directed graph has a valid ordering if and only if it has no cycle. If courses 1, 2, and 3 require each other in a loop (1 needs 2, 2 needs 3, 3 needs 1), there's no starting point; none of them can ever become eligible. So the whole problem collapses to: build the prerequisite graph, and detect whether it contains a cycle.

---

🚩 Pattern-Recognition Cue

"Course A requires course B first — can everything be completed?" is the cue for cycle detection in a directed graph, most naturally solved with topological sort (Kahn's algorithm): repeatedly take courses with no remaining prerequisites; if you ever get stuck with courses left but none available, that's a cycle.

---

🐢 Brute Force

Kahn's algorithm, but recompute each candidate course's in-degree by rescanning the full remaining edge list every round, instead of maintaining a running count.

func canFinishBruteForce(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    var remainingEdges = prerequisites.map { ($0[0], $0[1]) }  // (course, prereq)
    var takenCount = 0
    var taken = Array(repeating: false, count: numCourses)

    while takenCount < numCourses {
        var foundZeroIndegree = false
        for course in 0..<numCourses where !taken[course] {
            // Recompute in-degree for `course` from scratch: does any
            // remaining edge still require an untaken prerequisite?
            let hasUnmetPrereq = remainingEdges.contains { edge in
                edge.0 == course && !taken[edge.1]
            }
            if !hasUnmetPrereq {
                taken[course] = true
                takenCount += 1
                remainingEdges.removeAll { $0.0 == course }
                foundZeroIndegree = true
                break
            }
        }
        if !foundZeroIndegree { return false }   // nothing left with zero in-degree -> cycle
    }
    return true
}

Big-O: O(V² · E) roughly — up to V outer rounds, each scanning up to V courses, each course scan rescanning up to E remaining edges.

---

🚀 Optimal

Kahn's algorithm with a maintained in-degree array and a queue of courses whose prerequisites are all satisfied — each edge is examined exactly once overall, when its source course is finally taken.

func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    var adjacency = Array(repeating: [Int](), count: numCourses)
    var indegree = Array(repeating: 0, count: numCourses)

    for edge in prerequisites {
        let course = edge[0], prereq = edge[1]
        adjacency[prereq].append(course)
        indegree[course] += 1
    }

    var queue = (0..<numCourses).filter { indegree[$0] == 0 }
    var head = 0
    var taken = 0

    while head < queue.count {
        let course = queue[head]
        head += 1
        taken += 1
        for next in adjacency[course] {
            indegree[next] -= 1
            if indegree[next] == 0 {
                queue.append(next)
            }
        }
    }

    return taken == numCourses
}

// smoke test
print(canFinish(2, [[1,0]]))                  // true
print(canFinish(2, [[1,0],[0,1]]))            // false
print(canFinish(5, [[1,0],[2,1],[3,2],[4,3]])) // true

Big-O: O(V + E) time — building the adjacency list and in-degree array is O(V + E), and the BFS-like queue processing visits each vertex once and each edge once. O(V + E) space.

---

🔑 The Key Insight

Both approaches implement the same core idea — repeatedly remove courses that currently have no unmet prerequisites, and see if every course eventually gets removed. The brute force re-derives "does this course have zero remaining prerequisites?" from the full edge list every single round, throwing away all the bookkeeping it did in previous rounds. The optimal version instead maintains that answer incrementally: indegree is decremented exactly when (and only when) a prerequisite is actually taken, so a course becomes queue-eligible the instant its count hits zero — no rescanning required. That's the same incremental-maintenance idea as every brute-force/optimal pair in this chapter: pay once per edge, not once per edge per round.

---

🔗 Related Chapters

• Graphs — prerequisites naturally form a directed graph; "can all courses be finished" is a cycle-detection question on that graph.
• Topological Sort — Kahn's algorithm (in-degree + queue) is the canonical BFS-flavored topological sort, and this problem is its most direct application: a valid order exists iff no cycle exists.
• Queues and Deques — the index-based head pointer avoids O(n) removeFirst() calls, consistent with every other queue-driven BFS in this wiki.

---

🧸 Memory Sentence

Course Schedule is topological sort in disguise — repeatedly free up courses with zero remaining prerequisites, and if you run out of courses to free before running out of courses, there's a cycle.

---

✅ Check Your Understanding

1. Why does taken == numCourses at the end correctly detect a cycle, even though the code never explicitly checks for one?
2. In the optimal version, why is it safe to decrement indegree[next] only when course is popped from the queue, rather than when the edge is first built into adjacency?
3. Construct a small example (3–4 courses) with a cycle that does not involve every course, and trace through canFinish to see exactly where taken stops short of numCourses.

---

⬅️ Previous: Walls and Gates · Next: Course Schedule II ➡️