LeetCode 1462 - Course Schedule IV

LeetCode Problem 1462

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a directed acyclic graph representing course dependencies. Each course is a node, and a prerequisite relationship [a, b] means there is a directed edge from a to b. In other words, course a must be completed before course b.

The important detail is that prerequisites are transitive. If course 0 is required before course 1, and course 1 is required before course 2, then course 0 is also considered a prerequisite of course 2. The problem asks us to answer many such reachability questions efficiently.

For each query [u, v], we must determine whether there exists a path from u to v in the graph. If such a path exists, then u is a prerequisite of v.

The input consists of:

• numCourses, the total number of nodes in the graph
• prerequisites, the directed edges
• queries, the reachability checks we need to answer

The output is a boolean array where each position corresponds to one query.

The constraints are very important for selecting the right algorithm:

• numCourses <= 100
• queries <= 10^4

The graph itself is small, but the number of queries can be large. This strongly suggests preprocessing the graph once, then answering each query in constant time.

The graph is guaranteed to have no cycles, meaning it is a Directed Acyclic Graph, or DAG. This guarantee simplifies traversal logic because we never need to worry about infinite loops caused by cycles.

Several edge cases are important:

• There may be no prerequisite relationships at all.
• Queries may ask about unrelated nodes.
• Dependencies may be indirect across many intermediate courses.
• Multiple prerequisite chains may converge into the same course.
• The graph can be disconnected.

A naive solution that performs a fresh traversal for every query may still work for these constraints, but there is a more elegant preprocessing approach that answers every query efficiently.

Approaches

Brute Force Approach

The brute-force idea is straightforward. For every query [u, v], perform a graph traversal starting from u and check whether v is reachable.

We can use either Depth-First Search or Breadth-First Search for each query:

1. Build an adjacency list from the prerequisite pairs.
2. For every query:

• Start a DFS or BFS from u
• Search until either v is found or traversal ends

3. Return whether v was reachable

This works because graph traversal correctly determines reachability in a directed graph.

However, this becomes inefficient when there are many queries. If we perform a traversal for every query, we repeatedly explore the same graph structure many times.

With:

• up to 10^4 queries
• up to 100 nodes

the repeated traversals create unnecessary overhead.

Optimal Approach

The key insight is that the graph is small, but the number of queries is large.

Instead of answering queries independently, we can preprocess all prerequisite relationships in advance.

We create a matrix:

reachable[a][b]

which stores whether course a is a prerequisite of course b.

Since the graph has only 100 nodes, we can compute transitive reachability for all node pairs efficiently.

One elegant way to do this is the Floyd-Warshall transitive closure technique.

The idea is:

• Initialize direct prerequisite relationships

• Gradually allow intermediate nodes

• If:

• a -> k

• and k -> b

• then:

• a -> b

After preprocessing, every query becomes a constant-time lookup.

This is ideal because:

• preprocessing cost is small for n <= 100
• query answering becomes extremely fast

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q × (V + E))	O(V + E)	Runs DFS/BFS for every query
Optimal	O(V³ + q)	O(V²)	Precomputes all prerequisite relationships

Algorithm Walkthrough

We use Floyd-Warshall style transitive closure computation.

Step 1: Create the Reachability Matrix

We create a 2D boolean matrix:

reachable[i][j]

This matrix represents whether course i is a prerequisite of course j.

Initially, every value is False.

Step 2: Mark Direct Prerequisites

For every prerequisite pair [a, b]:

reachable[a][b] = True

This establishes all direct edges in the graph.

Step 3: Use Intermediate Nodes

We now attempt to improve reachability information by allowing intermediate nodes.

For every intermediate course k:

1. Check every possible start course i
2. Check every possible destination course j
3. If:

• i can reach k
• and k can reach j

4. Then:

• i can also reach j

The update becomes:

reachable[i][j] |= reachable[i][k] and reachable[k][j]

This progressively computes indirect prerequisite chains.

Step 4: Answer Queries

For every query [u, v], simply return:

reachable[u][v]

This is now an O(1) lookup.

Why it works

The algorithm works because Floyd-Warshall systematically considers every node as a possible intermediate connection point.

After processing node k, the matrix correctly represents all paths that use only nodes 0..k as intermediates.

By the end, every possible path in the graph has been considered. Therefore, reachable[a][b] is true if and only if there exists a directed path from a to b.

Python Solution

from typing import List

class Solution:
    def checkIfPrerequisite(
        self,
        numCourses: int,
        prerequisites: List[List[int]],
        queries: List[List[int]]
    ) -> List[bool]:

        reachable = [
            [False] * numCourses
            for _ in range(numCourses)
        ]

        # Direct prerequisites
        for prereq, course in prerequisites:
            reachable[prereq][course] = True

        # Floyd-Warshall transitive closure
        for intermediate in range(numCourses):
            for start in range(numCourses):
                if reachable[start][intermediate]:
                    for end in range(numCourses):
                        if reachable[intermediate][end]:
                            reachable[start][end] = True

        # Answer queries
        result = []

        for u, v in queries:
            result.append(reachable[u][v])

        return result

The implementation begins by allocating a numCourses × numCourses boolean matrix. Each entry represents whether one course is reachable from another.

Next, we populate all direct prerequisite relationships from the input array.

The core of the algorithm is the triple nested loop. The outer loop selects an intermediate node. The inner loops determine whether a path can be improved by passing through that intermediate node.

An optimization is included:

if reachable[start][intermediate]:

There is no reason to check all destinations if the start node cannot even reach the intermediate node.

Finally, queries are answered using direct matrix lookups, which makes each query extremely fast.

Go Solution

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {

	reachable := make([][]bool, numCourses)

	for i := 0; i < numCourses; i++ {
		reachable[i] = make([]bool, numCourses)
	}

	// Direct prerequisites
	for _, edge := range prerequisites {
		prereq := edge[0]
		course := edge[1]

		reachable[prereq][course] = true
	}

	// Floyd-Warshall transitive closure
	for intermediate := 0; intermediate < numCourses; intermediate++ {
		for start := 0; start < numCourses; start++ {

			if reachable[start][intermediate] {

				for end := 0; end < numCourses; end++ {

					if reachable[intermediate][end] {
						reachable[start][end] = true
					}
				}
			}
		}
	}

	// Answer queries
	result := make([]bool, 0, len(queries))

	for _, query := range queries {
		u := query[0]
		v := query[1]

		result = append(result, reachable[u][v])
	}

	return result
}

The Go implementation closely mirrors the Python version.

The primary difference is explicit slice allocation. Go requires manually constructing the 2D boolean matrix using nested make calls.

Go slices default to zero values, so all entries naturally begin as false.

No integer overflow concerns exist because all operations involve small indices and boolean values.

Worked Examples

Example 1

Input:

numCourses = 2
prerequisites = [[1,0]]
queries = [[0,1],[1,0]]

Initial Matrix

From \ To	0	1
0	F	F
1	T	F

This means:

1 -> 0

Processing Intermediate Node 0

No additional paths are discovered.

Processing Intermediate Node 1

No additional paths are discovered.

Final matrix:

From \ To	0	1
0	F	F
1	T	F

Query Results

Query	Result
[0,1]	False
[1,0]	True

Output:

[false, true]

Example 2

Input:

numCourses = 2
prerequisites = []
queries = [[1,0],[0,1]]

Initial Matrix

From \ To	0	1
0	F	F
1	F	F

No prerequisites exist.

No updates occur during Floyd-Warshall processing.

Query Results

Query	Result
[1,0]	False
[0,1]	False

Output:

[false, false]

Example 3

Input:

numCourses = 3
prerequisites = [[1,2],[1,0],[2,0]]
queries = [[1,0],[1,2]]

Initial Matrix

From \ To	0	1	2
0	F	F	F
1	T	F	T
2	T	F	F

Processing Intermediate Node 0

No new paths discovered.

Processing Intermediate Node 1

No new paths discovered.

Processing Intermediate Node 2

We already know:

1 -> 2
2 -> 0

Therefore:

1 -> 0

was already true.

Final matrix:

From \ To	0	1	2
0	F	F	F
1	T	F	T
2	T	F	F

Query Results

Query	Result
[1,0]	True
[1,2]	True

Output:

[true, true]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(V³ + Q)	Floyd-Warshall preprocessing plus constant-time query lookups
Space	O(V²)	Reachability matrix storage

The dominant cost comes from the triple nested loops used for transitive closure computation.

Since numCourses <= 100, the maximum number of operations is approximately:

100³ = 1,000,000

which is very manageable.

The query phase is extremely efficient because every query becomes a direct matrix lookup.

Test Cases

from typing import List

class Solution:
    def checkIfPrerequisite(
        self,
        numCourses: int,
        prerequisites: List[List[int]],
        queries: List[List[int]]
    ) -> List[bool]:

        reachable = [
            [False] * numCourses
            for _ in range(numCourses)
        ]

        for prereq, course in prerequisites:
            reachable[prereq][course] = True

        for intermediate in range(numCourses):
            for start in range(numCourses):
                if reachable[start][intermediate]:
                    for end in range(numCourses):
                        if reachable[intermediate][end]:
                            reachable[start][end] = True

        return [reachable[u][v] for u, v in queries]

solution = Solution()

# Example 1
assert solution.checkIfPrerequisite(
    2,
    [[1, 0]],
    [[0, 1], [1, 0]]
) == [False, True]  # direct prerequisite relationship

# Example 2
assert solution.checkIfPrerequisite(
    2,
    [],
    [[1, 0], [0, 1]]
) == [False, False]  # completely disconnected graph

# Example 3
assert solution.checkIfPrerequisite(
    3,
    [[1, 2], [1, 0], [2, 0]],
    [[1, 0], [1, 2]]
) == [True, True]  # indirect and direct prerequisites

# Single chain
assert solution.checkIfPrerequisite(
    4,
    [[0, 1], [1, 2], [2, 3]],
    [[0, 3], [1, 3], [3, 0]]
) == [True, True, False]  # long transitive chain

# Multiple disconnected components
assert solution.checkIfPrerequisite(
    6,
    [[0, 1], [2, 3], [4, 5]],
    [[0, 1], [0, 3], [2, 3], [4, 5]]
) == [True, False, True, True]  # separate components

# Diamond dependency structure
assert solution.checkIfPrerequisite(
    4,
    [[0, 1], [0, 2], [1, 3], [2, 3]],
    [[0, 3], [1, 2], [2, 3]]
) == [True, False, True]  # multiple paths to same node

# No prerequisites
assert solution.checkIfPrerequisite(
    5,
    [],
    [[0, 1], [1, 2], [3, 4]]
) == [False, False, False]  # empty graph

# Dense graph
assert solution.checkIfPrerequisite(
    4,
    [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]],
    [[0,3],[1,3],[2,0]]
) == [True, True, False]  # heavily connected DAG

Test Summary

Test	Why
Example 1	Validates direct prerequisite relationships
Example 2	Validates behavior with no edges
Example 3	Validates transitive prerequisites
Single chain	Tests long indirect dependency propagation
Multiple disconnected components	Ensures unrelated subgraphs remain independent
Diamond dependency structure	Verifies multiple prerequisite paths
No prerequisites	Confirms all queries return false
Dense graph	Stresses transitive closure updates

Edge Cases

One important edge case is when there are no prerequisites at all. In this situation, every course is independent, and every query should return False. A buggy implementation might accidentally infer relationships from uninitialized memory or incorrect defaults. Our implementation handles this correctly because the reachability matrix starts entirely as False, and no updates occur.

Another important case is long indirect prerequisite chains. For example:

0 -> 1 -> 2 -> 3 -> 4

A naive implementation that only checks direct edges would fail to recognize that 0 is a prerequisite of 4. The Floyd-Warshall transitive closure computation correctly propagates reachability across arbitrarily long chains.

A third important edge case is disconnected graph components. Some courses may belong to entirely separate dependency trees. For example:

0 -> 1

2 -> 3

Queries between the two components should always return False. Since the algorithm only updates reachability when valid connecting paths exist, disconnected components remain isolated throughout computation.

Another subtle edge case involves multiple paths between the same nodes. Consider:

0 -> 1 -> 3
0 -> 2 -> 3

The algorithm must still correctly mark 0 -> 3 exactly once regardless of how many distinct paths exist. The boolean reachability matrix naturally handles this because once an entry becomes True, repeated discoveries do not affect correctness.