Course Schedule IV - Video Solutions

Problem Overview: You’re given n courses and a list of prerequisite pairs where [a, b] means course a must be taken before b. For multiple queries [u, v], determine whether u is a direct or indirect prerequisite of v. The challenge is answering many reachability queries efficiently on a directed graph.

Approach 1: Union-Find with Path Compression (Near O((E + Q) α(n)) time, O(n) space)

This approach treats prerequisite chains similarly to disjoint-set structures. Each course maintains a representative ancestor, and find() uses path compression to quickly jump to earlier prerequisites in the chain. While processing prerequisite edges, union operations connect dependent courses with their prerequisite roots, effectively collapsing long prerequisite paths. When answering a query (u, v), compressed parent links allow fast checks along the chain without repeatedly traversing the entire dependency path. This technique works well when prerequisite relationships form long chains and queries are frequent, because path compression dramatically reduces repeated traversal costs.

The key insight is that many queries ask about the same prerequisite paths. After the first lookup, path compression flattens the structure so future checks become almost constant time. This behaves similarly to optimizing repeated traversals in a graph dependency structure.

Approach 2: Floyd-Warshall Transitive Closure (O(n³) time, O(n²) space)

Since the number of courses is small (≤100), computing full transitive closure is practical. Build a boolean matrix reachable[i][j] that indicates whether course i is a prerequisite of j. Initialize it using the given prerequisite edges. Then run the Floyd-Warshall dynamic programming update: for every intermediate course k, update reachable[i][j] |= reachable[i][k] && reachable[k][j]. This gradually propagates indirect dependencies through all possible intermediate courses.

After preprocessing, each query becomes a constant-time lookup in the matrix. This method is straightforward and very reliable for dense prerequisite graphs. Conceptually, it computes reachability across the entire DFS/BFS-style dependency graph without running a traversal for every query.

Recommended for interviews: Floyd-Warshall is usually the expected answer because it directly computes the transitive closure and guarantees O(1) query time after preprocessing. The Union-Find compression idea shows deeper understanding of structural optimization and repeated queries, but interviewers typically prefer the clarity and determinism of the Floyd-Warshall approach for this problem size.