Domain 2MediumMEDIUM

Course Schedule IV

Precompute transitive closure using Floyd-Warshall to answer reachability queries in O(1) time.

Domain: medium•Updated: 2026-09-16
#Floyd-Warshall#Adjacency Matrix#O(N^3)#Transitive Closure

Problem Breakdown

We are given nn courses labeled 0 to n-1. We have a list of direct prerequisites where [u, v] implies course u must be taken before course v, defining a directed edge from u to v. Additionally, we receive multiple queries asking if there is an indirect or direct path from one course to another (i.e., is A a prerequisite of B?).

Key Inputs:

  • n: Number of courses.
  • prerequisites: List of [from_course, to_course] pairs defining the DAG structure.
  • queries: List of [u, v] asking if there exists a path from u to v.

Key Outputs:

  • A list of booleans corresponding to each query in order.

Constraints & Edge Cases:

  • nn is small (≤100\le 100), but the number of queries can be large (10410^4). This suggests we should not process every query independently if it involves graph traversal, as that would lead to Time Limit Exceeded (TLE) in Python. We need a precomputation strategy.
  • The graph is guaranteed acyclic (DAG), so no infinite loops during traversal logic.
  • Queries might ask about non-existent paths or disconnected components; these should return false.

Intuition

A naive approach would be to run a Breadth-First Search (BFS) or Depth-First Search (DFS) from the source course for every single query to check reachability. Complexity of Brute Force: For each query, we traverse O(V+E)O(V + E) nodes/edges. With QQ queries and potentially dense graphs (E≈V2E \approx V^2), this results in roughly O(Q⋅N2)O(Q \cdot N^2). Given N=100N=100 and Q=104Q=10^4, operations could approach 10810^8, which is risky for Python’s execution time limits.

Optimal Insight: Since the number of courses (nn) is very small, we can precompute the reachability between all pairs of nodes (Transitive Closure). Once we know if u reaches v, any query takes O(1)O(1) to answer. We can compute this closure using the Floyd-Warshall algorithm or by running a BFS/DFS from every node once and storing results in an adjacency matrix. Given N=100N=100, Floyd-Warshall’s complexity of O(N3)≈1,000,000O(N^3) \approx 1,000,000 operations is negligible compared to processing the queries efficiently.

Approach

  1. Initialize Matrix: Create a boolean adjacency matrix reach of size n×nn \times n. Initialize all values to False.
  2. Populate Direct Edges: Iterate through prerequisites. For each [u, v], set reach[u][v] = True. Note that the problem defines prerequisites such that if we have a pair [1,0], it means course 1 is required for course 0 (edge 1→01 \to 0).
  3. Compute Transitive Closure: Use Floyd-Warshall logic to fill in indirect paths. For every intermediate node k from 0 to n-1:
    • If there is a path from i to k AND a path from k to j, then mark that there is a path from i to j.
    • Update: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
  4. Answer Queries: Iterate through the queries list. For each query [u, v], check if reach[u][v] is true. Append result to output list.

Complexity Analysis

  • Time Complexity: O(N3+Q)O(N^3 + Q). The Floyd-Warshall loop runs in cubic time relative to the number of courses (N=100  ⟹  1,000,000N=100 \implies 1,000,000 ops). Answering queries takes linear time with respect to query count. This is highly efficient given constraints.
  • Space Complexity: O(N2)O(N^2). We store an adjacency matrix for the reachability information (100×100100 \times 100 booleans), which uses minimal memory compared to input storage requirements.

Solution

from typing import List

class Solution:
    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # Initialize reachability matrix with False (0)
        is_reachable = [[False] * n for _ in range(n)]

        # Populate direct edges from prerequisites input
        # Note: [u, v] means u must be taken before v -> edge u -> v
        for u, v in prerequisites:
            is_reachable[u][v] = True
            
        # Floyd-Warshall Algorithm to compute Transitive Closure
        # k iterates through intermediate nodes
        for k in range(n):
            for i in range(n):
                if is_reachable[i][k]:  # If path exists from i -> k
                    row_k = is_reachable[k]
                    for j in range(n):
                        if row_k[j]:   # And path exists from k -> j
                            is_reachable[i][j] = True

        # Answer queries using the precomputed matrix
        result = []
        for u, v in queries:
            result.append(is_reachable[u][v])
            
        return result