This problem requires determining whether a course is a prerequisite for another using a directed acyclic graph representation. By building a reachability matrix and processing nodes in topological order, we can answer all queries efficiently. Both Depth-First Search and Breadth-First Search approaches are applicable but topological sorting with indegree tracking provides optimal clarity and speed.
Problem Statement
You are given a total of numCourses courses labeled from 0 to numCourses - 1. Each element in prerequisites is a pair [ai, bi], indicating that course ai must be completed before course bi. You need to process multiple queries to check if one course is a prerequisite of another.
Prerequisites can be indirect, meaning if course a is required before b, and b before c, then a is indirectly required before c. Given an array queries of pairs [uj, vj], determine for each query whether course uj is a prerequisite of course vj, considering both direct and indirect prerequisites.
Examples
Example 1
Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
The pair [1, 0] indicates that you have to take course 1 before you can take course 0. Course 0 is not a prerequisite of course 1, but the opposite is true.
Example 2
Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
There are no prerequisites, and each course is independent.
Example 3
Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]
Example details omitted.
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 <= 104
- 0 <= ui, vi <= numCourses - 1
- ui != vi
Solution Approach
Build a Graph and Track Indegree
Create an adjacency list for all courses and an indegree array. Courses with indegree zero can be processed first. This setup mirrors topological sort preparation and ensures we correctly propagate prerequisite relationships.
Compute Reachability via Topological Ordering
Use a queue to process courses in topological order. For each course, mark all reachable courses in a matrix isReachable[i][j]. This ensures indirect prerequisites are accounted for, and each query can later be answered in O(1) time.
Answer Queries Using the Reachability Matrix
Iterate through queries and check isReachable[uj][vj] for each pair. Using the precomputed reachability matrix ensures constant time lookups, avoiding repeated DFS or BFS for each query, which prevents TLE in dense graphs.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N^3 + Q) |
| Space | O(N^2) |
Time complexity is O(N^3 + Q) because building the reachability matrix involves O(N^3) operations for N courses, and answering Q queries is O(Q). Space complexity is O(N^2) to store the reachability matrix.
What Interviewers Usually Probe
- Are you considering both direct and indirect prerequisites?
- Can you optimize repeated queries without running DFS each time?
- How does topological ordering simplify the prerequisite propagation?
Common Pitfalls or Variants
Common pitfalls
- Ignoring indirect prerequisites leads to incorrect query answers.
- Attempting DFS/BFS per query may exceed time limits on large inputs.
- Failing to initialize or update the reachability matrix correctly during topological processing.
Follow-up variants
- Check if all courses can be completed given the same prerequisites graph.
- Determine the minimum number of courses required to satisfy a set of query constraints.
- Compute the longest chain of prerequisites instead of answering individual queries.
How GhostInterview Helps
- GhostInterview provides a structured topological sort solution and builds the isReachable matrix efficiently.
- It highlights failure modes like repeated DFS per query and guides toward O(1) query lookup.
- The solver walkthrough emphasizes indegree updates and propagation logic to handle indirect prerequisites.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does Course Schedule IV follow?
It follows a graph indegree plus topological ordering pattern, where building a reachability matrix lets us answer all queries efficiently.
Can DFS alone solve Course Schedule IV?
DFS can identify reachability but may be inefficient per query; topological ordering with an isReachable matrix handles multiple queries faster.
Why do we need a reachability matrix?
It precomputes direct and indirect prerequisites so each query can be answered in constant time, avoiding repeated graph traversal.
What are the main pitfalls in solving Course Schedule IV?
Common mistakes include ignoring indirect prerequisites, running DFS per query, and incorrectly updating reachability during topological processing.
How do topological sort and indegree tracking help here?
They ensure courses are processed in prerequisite order, propagating reachability correctly and efficiently without revisiting nodes unnecessarily.
Need direct help with Course Schedule IV instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Course Schedule IV from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Sort items into groups while respecting dependencies using graph indegree tracking and topological ordering patterns effectively.
Open problem page#802 Find Eventual Safe StatesSolve the problem of finding eventual safe states in a directed graph using depth-first search and topological sorting.
Open problem page#2328 Number of Increasing Paths in a GridSolve Number of Increasing Paths in a Grid by turning cell comparisons into a DAG and counting paths with topological DP.
Open problem page