{ }SolveLogs
⌕
Home / Graphs / #1462
LeetCode #1462 Medium

Course Schedule IV

Course Schedule IV is LeetCode 1462 (Medium). There are numCourses courses labelled 0 to numCourses - 1, and a list prerequisites where each pair [a, b] means course a must be taken before course b.

  • Prerequisites chain: if a comes before b and b before c, then a is a prerequisite of c too, even though no pair says so.
  • Each query [u, v] asks whether u is a prerequisite of v, directly or through a chain. Return one boolean per query.
  • The graph has no cycles, numCourses ≤ 100 and there are up to 10⁴ queries, so answers should be precomputed rather than searched per query.
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 <= 10⁴
  • 0 <= ui, vi <= numCourses - 1
  • ui != vi
graphtransitive-closuretopological-sort
Open on LeetCode ↗
02

Intuition

Each query in the course schedule iv LeetCode problem asks whether a chain of arrows leads from u to v. Searching the graph once per query repeats the same work up to 10⁴ times. Instead, compute once, for every course v, the set required[v] of all courses that must come before it. That all-pairs reachability is the transitive closure, and afterwards each query is one lookup.

The sets build on each other: for an arrow u → v, everything required before u, plus u itself, is required before v. That copy is only safe once required[u] is complete, and topological order guarantees exactly that.

How to spot this pattern

Many is X reachable from Y questions against one fixed graph mean precompute reachability once. On a DAG, a node's answer is built from its predecessors' answers, so topological order is the natural fill order. On a small graph (n ≤ 100) a Floyd-Warshall boolean matrix does the same job in three nested loops.

03

Approach

Try it first

Before reading on, decide what to store per course so that any query is one lookup, and in what order the courses must be processed so that nothing is copied before it is complete. Aim for O(n·E + Q) time.

Two ways to solve it

Kahn's algorithm with setsBest
Time O(n·E + Q)Space O(n²)

Process courses in topological order and push each course's prerequisite set to the courses it unlocks.

  • Fast on sparse input: work follows the edges, not n³.
  • Order-safe: a set is complete before it is copied.
  • More code: in-degrees, a queue and a set per course.

The better choice when there are few prerequisites.

Solution & demo ↓
Floyd-Warshall
Time O(n³ + Q)Space O(n²)

Fill a boolean matrix reach, then let every course k in turn act as a middle step between pairs.

  • Short: three nested loops and no queue.
  • Fixed cost: about 10⁶ steps at n = 100.
  • Watch out: k must be the outermost loop.

Fine here because n is tiny.

Code ↓

Both build the full transitive closure, but Kahn's work grows with the number of prerequisites while Floyd-Warshall always pays n³. The steps, code and live demo below follow Kahn's algorithm; the Floyd-Warshall code comes after the demo.

1

Build the graph in the right direction

For each pair [a, b], add the arrow a → b and raise b's in-degree. Here the first course of a pair comes first, the opposite of Course Schedule I and II, so copying their edge code silently reverses every answer.

2

Seed the queue

Put every course with in-degree 0 in the queue. Nothing comes before them, so their required sets are empty and already final, which makes them safe to copy from.

3

Pop a course and push its set forward

For each arrow course → nxt:

  • merge required[course] into required[nxt];
  • add course itself to required[nxt];
  • lower nxt's in-degree, and queue it when that reaches 0.

A course is popped only after every arrow into it was handled, so its set is complete before anything copies it.

4

Answer each query with one lookup

Query [u, v] is true exactly when u is in required[v]. The set belongs to the later course and lists what must come before it, so the lookup is O(1).

04

Course Schedule IV solution in Python | C++ | Java

▶1class Solution:
▶2 def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]],
▶3 queries: List[List[int]]) -> List[bool]:
▶4 graph = [[] for _ in range(numCourses)]
▶5 indegree = [0] * numCourses
▶6 for pre, course in prerequisites:
▶7 graph[pre].append(course)
▶8 indegree[course] += 1
▶9 required = [set() for _ in range(numCourses)]
▶10 
▶11 queue = deque(c for c in range(numCourses) if indegree[c] == 0)
▶12 while queue:
▶13 course = queue.popleft()
▶14 for nxt in graph[course]:
▶15 required[nxt] |= required[course]
▶16 required[nxt].add(course)
▶17 indegree[nxt] -= 1
▶18 if indegree[nxt] == 0:
▶19 queue.append(nxt)
▶20 
▶21 return [u in required[v] for u, v in queries]
01234queueemptyrequiredv = 0v = 1v = 2v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]5 prerequisite pairs, every set empty
courses5
pairs5[a, b]: a before b
Each pair [a, b] says a must be taken before b, so draw the arrow a → b. Note the order: this is the reverse of Course Schedule I and II, where [a, b] means b comes first. The goal is to fill required[v], every course that must come before v, directly or through a chain. Then each query is one lookup.
01234queue0requiredv = 0v = 1v = 2v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]queue the courses with no prerequisite
queue[0]in-degree 0
Course 0 has no incoming arrow, so nothing is required first and the set is already complete: empty. It starts the queue. A course joins the queue only when every course pointing into it has been processed, which is what guarantees a set is final before anything copies it.
01234queueemptyrequiredv = 0v = 1v = 2v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]pop 0, its set is final
course0popped
required[0]{}final
Pop course 0. Every arrow into it has already been handled, so required[0] = {} is complete and safe to copy along its 2 outgoing arrows.
01234queueemptyrequiredv = 0v = 10v = 2v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]copy 0 and required[0] into 1
edge0 → 1
required[1]{0}added 0
in-degree 10all arrows in
Anything required before 0 is also required before 1, and so is 0 itself, so 1 receives {0}. New: 0. That was 1's last incoming arrow.
01234queue1requiredv = 0v = 10v = 2v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]1 joins the queue
in-degree 10
queue[1]
In-degree of 1 hit 0: every course pointing into it has been processed, so required[1] = {0} can no longer grow. Only now is it safe for 1 to pass its set on, so it joins the queue.
01234queue1requiredv = 0v = 10v = 20v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]copy 0 and required[0] into 2
edge0 → 2
required[2]{0}added 0
in-degree 20all arrows in
Anything required before 0 is also required before 2, and so is 0 itself, so 2 receives {0}. New: 0. That was 2's last incoming arrow.
01234queue12requiredv = 0v = 10v = 20v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]2 joins the queue
in-degree 20
queue[1, 2]
In-degree of 2 hit 0: every course pointing into it has been processed, so required[2] = {0} can no longer grow. Only now is it safe for 2 to pass its set on, so it joins the queue.
01234queue2requiredv = 0v = 10v = 20v = 3v = 4queries [u, v][0, 4][2, 1][4, 0]pop 1, its set is final
course1popped
required[1]{0}final
Pop course 1. Every arrow into it has already been handled, so required[1] = {0} is complete and safe to copy along its 1 outgoing arrow.
01234queue2requiredv = 0v = 10v = 20v = 301v = 4queries [u, v][0, 4][2, 1][4, 0]copy 1 and required[1] into 3
edge1 → 3
required[3]{0, 1}added 0, 1
in-degree 31still waiting
Anything required before 1 is also required before 3, and so is 1 itself, so 3 receives {0, 1}. New: 0, 1. 3 still has 1 unprocessed prerequisite, so its set may still grow.
01234queueemptyrequiredv = 0v = 10v = 20v = 301v = 4queries [u, v][0, 4][2, 1][4, 0]pop 2, its set is final
course2popped
required[2]{0}final
Pop course 2. Every arrow into it has already been handled, so required[2] = {0} is complete and safe to copy along its 1 outgoing arrow.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 4queries [u, v][0, 4][2, 1][4, 0]copy 2 and required[2] into 3
edge2 → 3
required[3]{0, 1, 2}added 2
in-degree 30all arrows in
Anything required before 2 is also required before 3, and so is 2 itself, so 3 receives {0, 2}. New: 2. 0 was already there by another route, and a set keeps one copy. That was 3's last incoming arrow.
01234queue3requiredv = 0v = 10v = 20v = 3012v = 4queries [u, v][0, 4][2, 1][4, 0]3 joins the queue
in-degree 30
queue[3]
In-degree of 3 hit 0: every course pointing into it has been processed, so required[3] = {0, 1, 2} can no longer grow. Only now is it safe for 3 to pass its set on, so it joins the queue.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 4queries [u, v][0, 4][2, 1][4, 0]pop 3, its set is final
course3popped
required[3]{0, 1, 2}final
Pop course 3. Every arrow into it has already been handled, so required[3] = {0, 1, 2} is complete and safe to copy along its 1 outgoing arrow.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4][2, 1][4, 0]copy 3 and required[3] into 4
edge3 → 4
required[4]{0, 1, 2, 3}added 0, 1, 2, 3
in-degree 40all arrows in
Anything required before 3 is also required before 4, and so is 3 itself, so 4 receives {0, 1, 2, 3}. New: 0, 1, 2, 3. That was 4's last incoming arrow.
01234queue4requiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4][2, 1][4, 0]4 joins the queue
in-degree 40
queue[4]
In-degree of 4 hit 0: every course pointing into it has been processed, so required[4] = {0, 1, 2, 3} can no longer grow. Only now is it safe for 4 to pass its set on, so it joins the queue.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4][2, 1][4, 0]course 4 is a prerequisite of nothing
course4popped
required[4]{0, 1, 2, 3}final
Pop course 4. No arrow leaves it, so there is no set to pass along. Its own set, {0, 1, 2, 3}, was final the moment it entered the queue.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4] true[2, 1][4, 0]query 1: look for 0 in required[4]
query[0, 4]
required[4]{0, 1, 2, 3}
answertrue
Is 0 required before 4? Look for 0 in row 4: it is there, so true. There is no direct arrow; the chain carried it here.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4] true[2, 1] false[4, 0]query 2: look for 2 in required[1]
query[2, 1]
required[1]{0}
answerfalse
Is 2 required before 1? Look for 2 in row 1: it is not, so false. No chain of arrows leads from 2 to 1.
01234queueemptyrequiredv = 0v = 10v = 20v = 3012v = 40123queries [u, v][0, 4] true[2, 1] false[4, 0] falseanswer [true, false, false]
query[4, 0]
required[0]{}
answerfalse
Is 4 required before 0? Look for 4 in row 0: it is not, so false. The arrows run the other way: 0 is required before 4. Every query costs one set lookup, because the closure was built once.
05

Floyd-Warshall (boolean matrix)

Start with reach[a][b] = True for each pair. For every middle course k, any i that reaches k also reaches everything k reaches; after all k, reach[u][v] answers each query.

▶1class Solution:
▶2 def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
▶3 reach = [[False] * numCourses for _ in range(numCourses)]
▶4 for a, b in prerequisites:
▶5 reach[a][b] = True
▶6 for k in range(numCourses):
▶7 for i in range(numCourses):
▶8 if reach[i][k]:
▶9 for j in range(numCourses):
▶10 if reach[k][j]:
▶11 reach[i][j] = True
▶12 return [reach[u][v] for u, v in queries]
06

Common pitfalls

Checking only direct prerequisites

✗ Wrong
return [v in graph[u] for u, v in queries]
✓ Right
return [u in required[v] for u, v in queries]

A prerequisite can be indirect. With pairs [0,1] and [1,2], course 0 must come before 2 although no pair says so; the adjacency list answers false.

Merging in input order instead of topological order

✗ Wrong
for a, b in prerequisites:
    required[b] |= required[a] | {a}
✓ Right
# pop courses from a Kahn queue, so required[a]
# is complete before it is copied

Pairs can arrive in any order. With [[1,2],[0,1]], the first line copies required[1] into 2 while it is still empty; 0 reaches 1 only afterwards, so [0, 2] wrongly answers false.

Copying the ancestors but not the course itself

✗ Wrong
required[nxt] |= required[course]
✓ Right
required[nxt] |= required[course]
required[nxt].add(course)

The course at the tail of the arrow is the most direct prerequisite of all. A course with no prerequisites of its own has an empty set, so without the add nothing ever reaches its dependants and every answer is false.

07

Complexity

Time
O(n·E + Q)
Space
O(n²)
Each of the E arrows triggers one set merge of up to n courses, so building the closure is O(n·E), and each of the Q queries is an O(1) set lookup. The sets hold at most n² entries in total.
08

Course Schedule I, II and IV side by side

The three share a name and a graph but ask different questions, and IV even reads its pairs the other way round.

ProblemPair [a, b] meansQuestionMethod
Course Schedule (207)b before aCan every course be finished?Kahn's algorithm or DFS cycle check
Course Schedule II (210)b before aGive one valid orderKahn's algorithm, return the pop order
Course Schedule IV (1462)a before bIs u a prerequisite of v, directly or not?Transitive closure: Kahn with sets, or Floyd-Warshall
09

Course Schedule IV FAQ

How do you solve Course Schedule IV on LeetCode?
  • Graph: arrow a → b for each pair [a, b], and in-degrees.
  • Order: Kahn's algorithm, starting from courses with in-degree 0.
  • Sets: for each arrow course → nxt, merge required[course] and course into required[nxt].
  • Queries: [u, v] is u in required[v].
  • Cost: O(n·E) to build, O(1) per query.
What is the transitive closure in Course Schedule IV?

It is the full comes-before relation: u is related to v whenever a chain of prerequisite arrows leads from u to v. Storing it as one set per course (or an n × n boolean matrix) turns every query into a lookup.

Why does the course schedule iv solution need topological order?

A course's set is copied into the courses that depend on it. If it is copied before all of its own prerequisites have arrived, the copy is incomplete and chains get cut. Kahn's algorithm only pops a course after every arrow into it has been processed, so each set is final when it is copied.

← Prev · #1456
Maximum Number of Vowels in a Substring
Next · #1466 →
Reorder Routes to Make All Paths Lead to City Zero