Course Schedule IV
01 · Problem
You are planning numCourses courses labelled 0 to numCourses - 1. Each prerequisites[i] = [a, b] says course a must be completed before course b. Prerequisite chains are transitive: if a comes before b and b comes before c, then a is also a prerequisite of c.
You are also given queries, where queries[j] = [u, v] asks: is course u a (direct or indirect) prerequisite of course v?
Return a boolean array answer where answer[j] is the answer to the j-th query, in the same order as queries. The prerequisite graph has no cycles.
02 · Examples
numCourses = 4, prerequisites = [[0,1],[1,2],[3,2]], queries = [[0,2],[2,0],[3,1],[3,2]]
[true,false,false,true]
0 -> 1 -> 2, so 0 is an indirect prerequisite of 2. Course 2 is not before 0. Course 3 only leads to 2, not to 1. Course 3 is a direct prerequisite of 2.
numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
[false,false]
With no prerequisites, no course depends on any other.
numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
[true,true]
Course 1 directly precedes both 0 and 2.
03 · Constraints
- 012 <= numCourses <= 100
- 020 <= prerequisites.length <= numCourses * (numCourses - 1) / 2
- 03All prerequisite pairs are distinct, a != b, and the graph is acyclic
- 041 <= queries.length <= 104
- 050 <= u, v <= numCourses - 1 and u != v
04 · Optimal complexity
- Time
- O(n^3 + q)
- Space
- O(n^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.