1462. Course Schedule IV
Problem Description
In this LeetCode problem, we are given a scenario similar to course scheduling at a university. Each course is identified by a unique number, ranging from 0
to numCourses - 1
. There are certain courses that must be completed before taking other courses. These prerequisites are expressed as an array of pairs, where each pair [a, b]
indicates that course a
must be taken before course b
.
The prerequisites can have an indirect relationship as well. Meaning, if course a
is a prerequisite for course b
, and course b
is a prerequisite for course c
, then indirectly, course a
is a prerequisite for course c
.
We also have an array of queries. Each query [u,v]
asks whether course u
is a prerequisite for course v
. The task is to write a function that returns a boolean array. Each boolean value corresponds to a query and determines whether the first course in the query is a prerequisite for the second one.
Flowchart Walkthrough
Letās analyze problem leetcode 1462. Course Schedule IV using the algorithm flowchart available here. Here is a step-by-step breakdown to determine the suitable algorithm:
Is it a graph?
- Yes: The problem involves determining the prerequisites among courses, which can be represented as a graph where nodes are courses and edges indicate that one course is a prerequisite for another.
Is it a tree?
- No: The prerequisite relationships can form cycles (e.g., mutual prerequisites), therefore the courseāprerequisite graph is not necessarily a tree.
Is the problem related to directed acyclic graphs (DAGs)?
- Yes: If we treat the prerequisites as directed edges (A ā B means B is a prerequisite for A), managing these prerequisites implies a need to handle these relationships, commonly a directed acyclic graph barring any circular prerequisites.
Topological Sort:
- We reach the node suggesting Topological Sort. Topological sorting of a directed graph is a linear ordering of its vertices such that for every directed edge UV from vertex U to vertex V, U comes before V in the ordering. Topological sorting is relevant here as knowing the order could help in determining if it's possible to complete a course given its dependencies.
Conclusion:
The flowchart points towards utilizing Topological Sort for analyzing prerequisites in a DAG for Course Schedule IV. Often, topological sorting is implemented using Depth-First Search in cases where you need to explore prerequisites (dependencies) recursively. Therefore, using DFS along with careful checks for cycles (to verify if the graph indeed remains acyclic) is recommended.
Intuition
The key challenge of this problem is dealing with both direct and indirect prerequisites. To solve this, we need an efficient way to determine the relationship between courses.
One approach to solve this problem lies in using graph theory, where nodes represent courses, and directed edges represent prerequisite relationships. We build a directed graph such that, for each prerequisite pair [a,b]
, we have a directed edge from a
to b
, implying that one must take course a
before course b
.
With the graph built, we can determine the reachability of each course from every other course. This means that, once we establish that we can reach course b
from course a
, we can say that a
is a prerequisite for b
. To achieve this, we implement a modified Floyd-Warshall algorithm or use transitive closure on the graph to find all reachable vertices from a given vertex.
The solution posted uses an approach similar to topological sorting, a sorting method used on directed acyclic graphs (DAGs). It maintains a list, g
, that holds the courses dependent on the current course and an array, indeg
, to store the number of prerequisite courses needed before one can take the course. The matrix f[i][j]
will be True
if course i
is a prerequisite of course j
.
Here's a step-by-step breakdown:
- Initialize a matrix
f
to record if one course is a prerequisite of another. - Create a graph
g
representing the course prerequisites and an indegree listindeg
. - Use a queue
q
to keep track of courses that have no prerequisites (indegree of 0). - Begin processing the queue, and for each course
i
taken fromq
,- Mark
f[i][j]
toTrue
for each coursej
that hasi
as a prerequisite. - Update the prerequisites for courses dependent on
j
to include the prerequisites fori
. - Decrease the indegree for each course
j
and if it becomes0
, add it to the queue.
- Mark
- Now
f
contains information about all direct and indirect prerequisites. - Iterate through the queries and return the boolean results from the
f
matrix.
Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.
Solution Approach
The implementation of this solution involves several key components typical to graph theory and breadth-first search (BFS) traversal, particularly adapted for the problem of determining prerequisites (which can be considered a form of transitive closure in a graph).
Here's how the solution approach works step-by-step:
-
Matrix Initialization: A 2D list
f
of sizen x n
is initialized toFalse
, wheren
is the number of courses. This list will keep track of prerequisite relationshipsāf[i][j]
beingTrue
represents that coursei
is a prerequisite for coursej
. -
Graph Representation: A graph
g
is created as a list of empty lists, whereg[i]
will eventually contain all the courses that directly require coursei
as a prerequisite. Theindeg
list holds the indegree of each course, which counts the number of prerequisites each course has. -
Building Graph and Indegree List: The prerequisites list is iterated over, and for each pair
[a, b]
, courseb
is added tog[a]
, and the indegree of courseb
is incremented. This constructs the initial directed graph and the indegree list. -
Queue Initialization for BFS: A queue
q
is initialized with all courses that have an indegree of 0, i.e., courses that can be taken without having taken any other courses first. -
BFS Traversal:
- While the queue is not empty, pop the front course
i
from the queue. - For each course
j
ing[i]
:- Set
f[i][j]
toTrue
, sincei
is a direct prerequisite forj
. - Iterate over all courses
h
(from0
ton-1
):- Update
f[h][j]
to be the logical OR of its current value andf[h][i]
. This line propagates the prerequisite information, meaning ifh
is a prerequisite fori
andi
forj
, thenh
becomes a prerequisite forj
.
- Update
- Decrement the indegree of course
j
. If the indegree ofj
now becomes 0, it means that all its prerequisites have been accounted for, and it can be added to the queue for further processing.
- Set
- While the queue is not empty, pop the front course
-
Answering Queries: Finally, a simple list comprehension is used to iterate over each query in queries and to append the respective boolean value from
f
that indicates whether the first course in the query is a prerequisite for the second course[f[a][b] for a, b in queries]
.
By using this approach, we leverage a matrix to keep track of prerequisites while using a BFS approach to iteratively determine and propagate these relationships. This sidesteps complex recursive calls or deep searching algorithms that might be less efficient with large numbers of courses and prerequisites.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, consider a small university with 4 courses (numbered from 0 to 3) and the following prerequisites: course 0 is a prerequisite for course 1 and course 2, and course 1 is a prerequisite for course 3. We also have queries asking if course 0 is a prerequisite for course 3, and if course 2 is a prerequisite for course 1.
Let's go through the steps to solve this:
-
Matrix Initialization: Initialize an
n x n
matrixf
with allFalse
, heren = 4
. This will reflect that no courses are prerequisites of others to begin with. -
Graph Representation: We create a graph represented as
g = [[], [], [], []]
. It's a list of lists where each outer list corresponds to a course and will eventually contain all the courses that directly require it as a prerequisite. -
Building Graph and Indegree List: The prerequisites array maybe
[[0,1], [0,2], [1,3]]
. From this, we populate our graphg
and an indegree listindeg
as follows:- Add course 1 to
g[0]
and course 2 tog[0]
(because course 0 is a prerequisite for both), incrementindeg[1]
andindeg[2]
. - Add course 3 to
g[1]
(because course 1 is a prerequisite for course 3) and incrementindeg[3]
. After this,g
would be[[1,2], [3], [], []]
andindeg
would be[0,1,1,1]
.
- Add course 1 to
-
Queue Initialization for BFS: Populate a queue
q
with courses that have an indegree of 0. In this case, course 0 has no prerequisites, soq = [0]
. -
BFS Traversal: Process the queue as per the algorithm:
- Pop course
0
fromq
. Its prerequisites will be courses1
and2
. - Mark
f[0][1]
andf[0][2]
toTrue
. - Propagate dependencies: For dependent course
1
, markf[0][3]
toTrue
(since course 0 is a prerequisite for course 1 which in turn is for course 3). Similarly, if there were courses dependent on2
, propagate the prerequisites for0
accordingly. - Decrease the indegree of courses
1, 2
by 1, and any course which now has an indegree 0 is added toq
. Consequently, courses1
and2
are added toq
. - Continue the process for courses
1
and2
. Since course1
has3
as a dependent, we markf[1][3]
toTrue
, but alsof[0][3]
is alreadyTrue
so it remains so. Now, indegree of3
becomes 0, and it is added toq
to process although3
has no dependents.
- Pop course
-
Answering Queries: For the queries, we simply check the
f
matrix: for the query[0, 3]
, we checkf[0][3]
which isTrue
. For the query[2, 1]
, we checkf[2][1]
which isFalse
. Therefore, the answer to the queries would be[True, False]
.
By progressing through the steps laid out in the solution approach using a small example with 4 courses and a simple prerequisite relationship, we have been able to establish a True
or False
value for each query, indicating whether one course is a prerequisite for another, considering direct and indirect prerequisite relationships.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
6 # Initialize a 2D array to keep track of prerequisite relationships
7 prereq_matrix = [[False] * numCourses for _ in range(numCourses)]
8 # Adjacency list representation of the graph
9 graph = [[] for _ in range(numCourses)]
10 # In-degree count array to keep track of prerequisites count for each course
11 indegree = [0] * numCourses
12
13 # Populate the graph and in-degree count from the prerequisites list
14 for course, next_course in prerequisites:
15 graph[course].append(next_course)
16 indegree[next_course] += 1
17
18 # Initialize a queue with all courses with no prerequisites
19 queue = deque([i for i, count in enumerate(indegree) if count == 0])
20
21 # Perform a topological sort to determine prerequisite relationships
22 while queue:
23 current_course = queue.popleft()
24 for next_course in graph[current_course]:
25 # Mark direct prerequisite relationship as true
26 prereq_matrix[current_course][next_course] = True
27 # Propagate the prerequisite information
28 for course in range(numCourses):
29 prereq_matrix[course][next_course] = prereq_matrix[course][next_course] or prereq_matrix[course][current_course]
30 # Reduce in-degree count and add course to queue if it has no remaining prerequisites
31 indegree[next_course] -= 1
32 if indegree[next_course] == 0:
33 queue.append(next_course)
34
35 # Process the queries to check if each query pair has a prerequisite relationship
36 return [prereq_matrix[start_course][end_course] for start_course, end_course in queries]
37
1class Solution {
2
3 public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
4 // Floyd-Warshall algorith to determine transitive closure of prerequisites
5 boolean[][] transitiveClosure = new boolean[numCourses][numCourses];
6 List<Integer>[] graph = new List[numCourses];
7 int[] inDegree = new int[numCourses]; // For topological sorting
8
9 // Initialize adjacency list
10 Arrays.setAll(graph, i -> new ArrayList<>());
11
12 // Build graph and in-degree array from prerequisites
13 for (int[] prerequisite : prerequisites) {
14 graph[prerequisite[0]].add(prerequisite[1]);
15 ++inDegree[prerequisite[1]]; // Increment in-degree of successor
16 }
17
18 // Queue used for topological sorting
19 Deque<Integer> queue = new ArrayDeque<>();
20
21 // Adding all nodes with in-degree 0 to queue
22 for (int i = 0; i < numCourses; ++i) {
23 if (inDegree[i] == 0) {
24 queue.offer(i);
25 }
26 }
27
28 // Perform topological sort (Kahn's algorithm)
29 while (!queue.isEmpty()) {
30 int course = queue.poll();
31
32 // Explore all neighbors of the current course
33 for (int neighbor : graph[course]) {
34
35 transitiveClosure[course][neighbor] = true;
36
37 // Update transitive closure for all nodes that lead to current
38 for (int preCourse = 0; preCourse < numCourses; ++preCourse) {
39 transitiveClosure[preCourse][neighbor] |= transitiveClosure[preCourse][course];
40 }
41
42 // Decrement in-degree of neighbor and if 0, add to queue
43 if (--inDegree[neighbor] == 0) {
44 queue.offer(neighbor);
45 }
46 }
47 }
48
49 // Prepare the answer list to fulfill queries
50 List<Boolean> answers = new ArrayList<>();
51
52 // Check in the transitive closure if prerequisites are met
53 for (int[] query : queries) {
54 answers.add(transitiveClosure[query[0]][query[1]]);
55 }
56
57 // Return the list of results for each query
58 return answers;
59 }
60}
61
1class Solution {
2public:
3 // This method determines if the second course in each query is a prerequisite of the first.
4 vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
5 // Create a 2D array to mark prerequisites.
6 bool isPrerequisite[numCourses][numCourses];
7 memset(isPrerequisite, false, sizeof(isPrerequisite));
8
9 // Adjacency list for graph representation.
10 vector<int> graph[numCourses];
11
12 // Array to track the number of incoming edges for each course.
13 vector<int> inDegree(numCourses, 0);
14
15 // Build the graph and update in-degrees.
16 for (const auto& prerequisite : prerequisites) {
17 graph[prerequisite[0]].push_back(prerequisite[1]);
18 ++inDegree[prerequisite[1]];
19 }
20
21 // Queue for BFS.
22 queue<int> courseQueue;
23
24 // Add courses with no prerequisites to the queue.
25 for (int i = 0; i < numCourses; ++i) {
26 if (inDegree[i] == 0) {
27 courseQueue.push(i);
28 }
29 }
30
31 // Process courses using BFS.
32 while (!courseQueue.empty()) {
33 int current = courseQueue.front();
34 courseQueue.pop();
35
36 for (int adjacentCourse : graph[current]) {
37 // Mark current as a direct prerequisite of adjacentCourse.
38 isPrerequisite[current][adjacentCourse] = true;
39
40 // Mark all the prerequisites of current as prerequisites of adjacentCourse as well.
41 for (int k = 0; k < numCourses; ++k) {
42 isPrerequisite[k][adjacentCourse] |= isPrerequisite[k][current];
43 }
44
45 // If the adjacentCourse has no other prerequisites, add it to the queue.
46 if (--inDegree[adjacentCourse] == 0) {
47 courseQueue.push(adjacentCourse);
48 }
49 }
50 }
51
52 // Now check the queries against the prerequisites map.
53 vector<bool> results;
54 for (const auto& query : queries) {
55 results.push_back(isPrerequisite[query[0]][query[1]]);
56 }
57
58 return results;
59 }
60};
61
1function checkIfPrerequisite(numCourses: number, prerequisites: number[][], queries: number[][]): boolean[] {
2 // Initialize prerequisite matrix, graph representation, and in-degree array
3 const prereqMatrix = Array.from({ length: numCourses }, () => Array(numCourses).fill(false));
4 const courseGraph: number[][] = Array.from({ length: numCourses }, () => []);
5 const inDegree: number[] = Array(numCourses).fill(0);
6
7 // Build the graph and populate in-degree array based on prerequisites
8 for (const [prereq, course] of prerequisites) {
9 courseGraph[prereq].push(course);
10 ++inDegree[course];
11 }
12
13 // Initialize queue for courses with no prerequisites
14 const queue: number[] = [];
15 for (let course = 0; course < numCourses; ++course) {
16 if (inDegree[course] === 0) {
17 queue.push(course);
18 }
19 }
20
21 // Process courses in topological order
22 while (queue.length) {
23 const currentCourse = queue.shift()!; // Non-null assertion as we know the queue is not empty
24
25 // Traverse all immediate next courses and update the prerequisite matrix
26 for (const nextCourse of courseGraph[currentCourse]) {
27 prereqMatrix[currentCourse][nextCourse] = true;
28
29 // Propagate prerequisite relations
30 for (let preCourse = 0; preCourse < numCourses; ++preCourse) {
31 prereqMatrix[preCourse][nextCourse] ||= prereqMatrix[preCourse][currentCourse];
32 }
33
34 // Decrement in-degree and add the course to queue if it has no remaining prerequisites
35 if (--inDegree[nextCourse] === 0) {
36 queue.push(nextCourse);
37 }
38 }
39 }
40
41 // Translate queries into an array of boolean results using the prerequisite matrix
42 return queries.map(([startCourse, endCourse]) => prereqMatrix[startCourse][endCourse]);
43}
44
Time and Space Complexity
Time Complexity
The given Python code performs multiple operations involving graphs and lists, so let's break down its time complexity:
-
Initialization of
f
andg
: The two lists are initialized with sizesn x n
andn
, respectively. Initializations run inO(n^2)
forf
andO(n)
forg
. -
Iterating over prerequisites list: The loop goes through the list of prerequisites, which in worst case will have
O(n^2)
elements (if every node is a prerequisite for every other node), and updates graphg
andindeg
. Each operation inside the loop takes constant time, so this step runs inO(E)
whereE
is the number of edges or prerequisites. -
Processing the graph: The while loop dequeues nodes with
indegree
of 0 and processes adjacent nodes. Each edge is considered once when its destination node'sindegree
becomes 0, and the for loop inside processesn
possible predecessors. This results inO(n + E)
operations for the while loop since every node and edge is considered once. But due to the nested for loops, we're actually consideringn
times the adjacent nodes for updatingf
which yieldsO(n * E)
. -
Answering queries: This is a direct access operation for each query in
f
which takesO(1)
time. There may beQ
queries, thus this would takeO(Q)
.
Combining all these, the overall time complexity is dominated by O(n * E)
, given that updating f
can take up to O(n)
time for each of the E
edges in the worst-case scenario. Therefore, the time complexity is O(n^2 + E + n * E + Q) = O(n * E + Q)
.
Space Complexity
The space complexity of the algorithm can be analyzed as follows:
-
Space for
f
:O(n^2)
since it stores boolean values for every possible pair of nodes. -
Space for
g
andindeg
:O(n)
for each, since they store a list of adjacent nodes and indegree counts for each node, respectively. -
Additional space for the queue
q
: In the worst case, this can store alln
nodes, soO(n)
.
So, the overall space complexity is the sum of these which gives O(n^2) + 2 * O(n) + O(n) = O(n^2)
as n^2
will dominate the space complexity for large n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Want a Structured Path to Master System Design Too? Donāt Miss This!