Skip to main content
Talentd

Course Schedule IV - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchGraphTopological Sort20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

  • For example, the pair [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 <= 100
  • 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
  • prerequisites[i].length == 2
  • 0 <= ai, bi <= numCourses - 1
  • ai != bi
  • All the pairs [ai, bi] are unique.
  • The prerequisites graph has no cycles.
  • 1 <= queries.length <= 104
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi

Approach Overview

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.

Approach 1: Union-Find with Path Compression

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Floyd-Warshall Algorithm

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Floyd's Algorithm

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Topological Sorting

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) space complexity to store the union-find data structures.

Floyd-Warshall Algorithm

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.

Floyd's Algorithm—
Topological Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Union-Find with Path CompressionNear 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)

Video Solution

Course Schedule IV - Leetcode 1462 - Python • NeetCodeIO • 18,174 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Course Schedule IV easy or hard?
Course Schedule IV is rated Medium difficulty on LeetCode with an acceptance rate around 60%. The main challenge is recognizing that the problem asks for transitive reachability across a directed graph rather than checking only direct prerequisites.
Course Schedule IV Python/Java solution
Both Python and Java implementations typically use a 2D boolean matrix for the Floyd-Warshall algorithm. The matrix stores whether course i is a prerequisite of course j, and triple nested loops propagate indirect dependencies before answering queries.
How to solve Course Schedule IV in O(n)?
Pure O(n) solutions are not typical for this problem because the graph may contain many indirect prerequisite paths. Practical solutions either compute full transitive closure using Floyd-Warshall in O(n^3) or optimize repeated queries using path compression or graph traversal caching techniques.
What is the best approach for Course Schedule IV?
Floyd-Warshall is the most reliable approach for Course Schedule IV. It precomputes the transitive closure of the prerequisite graph in O(n^3) time and O(n^2) space. After preprocessing, every query can be answered in O(1) time by checking a boolean matrix entry.
Is Course Schedule IV asked at Google/Amazon/Meta?
Graph reachability and prerequisite-style dependency problems are common in interviews at companies like Google, Amazon, and Meta. Variants of Course Schedule problems frequently appear because they test understanding of graphs, topological relationships, and transitive dependencies.
What data structure is used in Course Schedule IV?
The problem primarily uses graph data structures. Solutions often rely on adjacency lists or matrices, boolean reachability matrices for Floyd-Warshall, or disjoint-set (Union-Find) structures with path compression to speed up repeated dependency checks.
What is the time complexity of Course Schedule IV?
The common optimal solution uses Floyd-Warshall with O(n^3) preprocessing time and O(n^2) space. Once the transitive closure matrix is built, each query is answered in constant time O(1). Alternative approaches using path compression or graph traversal may achieve near O((E+Q) α(n)) depending on implementation.

Ready to solve this problem?

Practice Course Schedule IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree