There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.
[0, 1] indicates that you have to take course 0 before you can take course 1.Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.
You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.
Return a boolean array answer, where answer[j] is the answer to the jth query.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true] Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0. Course 0 is not a prerequisite of course 1, but the opposite is true.
Example 2:
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]] Output: [false,false] Explanation: There are no prerequisites, and each course is independent.
Example 3:
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] Output: [true,true]
Constraints:
2 <= numCourses <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != bi[ai, bi] are unique.1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != viProblem 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.
The Union-Find algorithm (also known as Disjoint Set Union, or DSU) can be used to efficiently determine the connected components of a graph. Using path compression and union by rank, it supports finding the connected component representatives in near constant time. By representing the courses as nodes and prerequisites as directed edges, we can enable union operations for direct prerequisite relationships.
This Python implementation uses a Union-Find data structure to manage and find the connected components. For each query, if the connected components of the courses match, then it means course u is an indirect prerequisite of course v. The union and find operations are modified by path compression to ensure efficiency.
Time Complexity: O(n + m) for n queries and m union operations, assuming almost constant time for find and union operations due to path compression.
Space Complexity: O(n) space complexity to store the union-find data structures.
The Floyd-Warshall algorithm is a classic algorithm for finding shortest paths in a directed graph with non-negative weights. In this context, it can be used to compute the transitive closure of the graph, meaning for every pair (i, j), we determine if there's a path from i to j. This matches our problem definition when deciding if one course is a prerequisite for another.
This Python solution applies the Floyd-Warshall algorithm to compute the reachability matrix of courses. By iterating through all triples of courses, we fill out the reach matrix to answer every query in constant time. This determines if a path (prerequisite chain) exists between any two courses.
Time Complexity: O(n^3) due to the three nested loops for each pair of courses.
Space Complexity: O(n^2) for the reachability matrix.
We create a 2D array f, where f[i][j] indicates whether node i can reach node j.
Next, we iterate through the prerequisites array prerequisites. For each item [a, b] in it, we set f[a][b] to true.
Then, we use Floyd's algorithm to compute the reachability between all pairs of nodes.
Specifically, we use three nested loops: first enumerating the intermediate node k, then the starting node i, and finally the ending node j. For each iteration, if node i can reach node k and node k can reach node j, then node i can also reach node j, and we set f[i][j] to true.
After computing the reachability between all pairs of nodes, for each query [a, b], we can directly return f[a][b].
The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
Similar to Solution 1, we create a 2D array f, where f[i][j] indicates whether node i can reach node j. Additionally, we create an adjacency list g, where g[i] represents all successor nodes of node i, and an array indeg, where indeg[i] represents the in-degree of node i.
Next, we iterate through the prerequisites array prerequisites. For each item [a, b] in it, we update the adjacency list g and the in-degree array indeg.
Then, we use topological sorting to compute the reachability between all pairs of nodes.
We define a queue q, initially adding all nodes with an in-degree of 0 to the queue. Then, we continuously perform the following operations: remove the front node i from the queue, then iterate through all nodes j in g[i], setting f[i][j] to true. Next, we enumerate node h, and if f[h][i] is true, we also set f[h][j] to true. After this, we decrease the in-degree of j by 1. If the in-degree of j becomes 0, we add j to the queue.
After computing the reachability between all pairs of nodes, for each query [a, b], we can directly return f[a][b].
The time complexity is O(n^3), and the space complexity is O(n^2), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Union-Find with Path Compression | Time Complexity: O(n + m) for n queries and m union operations, assuming almost constant time for find and union operations due to path compression. |
| Floyd-Warshall Algorithm | Time Complexity: O(n^3) due to the three nested loops for each pair of courses. |
| Floyd's Algorithm | — |
| Topological Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Path Compression | Near O((E + Q) α(n)) | O(n) | Large number of repeated queries where prerequisite chains repeat and path compression helps avoid repeated traversal |
| Floyd-Warshall (Transitive Closure) | O(n^3) | O(n^2) | Small n (≤100) with many queries; precompute full reachability and answer each query in O(1) |
Course Schedule IV - Leetcode 1462 - Python • NeetCodeIO • 16,829 views views
Watch 9 more video solutions →Practice Course Schedule IV with our built-in code editor and test cases.
Practice on FleetCode