Course Schedule IV

Course Schedule IV is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

Problem statement

Implement Solution.checkIfPrerequisite(numCourses, prerequisites, queries) for a directed graph of courses. Each course is identified by an integer from 0 through numCourses - 1. A pair [a, b] in prerequisites means course a must be completed before course b, creating a directed edge from a to b.

A course a is a prerequisite of course b when there is a directed path from a to b containing at least one edge. This includes indirect relationships through any number of intermediate courses.

For every pair [u, v] in queries, determine whether u is a prerequisite of v. Return a boolean array in the same order as queries, with true exactly when the corresponding prerequisite relationship exists. The prerequisite graph has no cycles, and no course is considered a prerequisite of itself.

Example 1:

Input: numCourses = 5, prerequisites = [[0,2],[2,4],[1,3]], queries = [[0,4],[0,3],[1,3],[4,0],[2,2]] Output: [true,false,true,false,false] Explanation: Course 0 reaches course 4 through course 2, but it does not reach course 3. A course is not its own prerequisite, so [2,2] is false.

Example 2:

Input: numCourses = 6, prerequisites = [[0,1],[0,2],[3,4]], queries = [[0,2],[0,4],[1,0],[3,4],[5,5]] Output: [true,false,false,true,false] Explanation: Courses 0 and 3 directly precede courses 2 and 4 respectively. There is no path from 0 to 4 or from 1 to 0, and course 5 is not its own prerequisite.

Example 3:

Input: numCourses = 7, prerequisites = [[1,0],[1,2],[0,3],[2,3],[3,5]], queries = [[1,5],[0,5],[2,5],[5,1],[4,5]] Output: [true,true,true,false,false] Explanation: Course 1 reaches course 5 through either course 0 or course 2, and both courses 0 and 2 also reach course 5. Courses 5 and 4 have no path to the queried targets.

Constraints:

- 1 <= numCourses <= 100 - 0 <= prerequisites.length <= numCourses (numCourses - 1) / 2 - Each element of prerequisites has exactly 2 integers. - 0 <= prerequisites[i][0], prerequisites[i][1] < numCourses. - prerequisites[i][0] != prerequisites[i][1], and the directed graph described by prerequisites has no cycles. - There are no duplicate prerequisite pairs. - 0 <= queries.length <= 10^4, and each query has exactly 2 integers in the range 0 through numCourses - 1.

Topics and companies

Topics: Graph, Topological Sort, Dynamic Programming.

How to practise Course Schedule IV on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(numCourses^3 + queries.size()) time and O(numCourses^2) space.

Open Course Schedule IV in the code editor, or read the Course Schedule IV editorial for a worked solution with its approach and complexity analysis.

Where Course Schedule IV sits in the DSA pattern sheet

Problems related to Course Schedule IV

Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.