1462. Course Schedule IV

MediumDepth-First SearchBreadth-First SearchGraphTopological Sort
Leetcode Link

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.

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:

  1. Initialize a matrix f to record if one course is a prerequisite of another.
  2. Create a graph g representing the course prerequisites and an indegree list indeg.
  3. Use a queue q to keep track of courses that have no prerequisites (indegree of 0).
  4. Begin processing the queue, and for each course i taken from q,
    • Mark f[i][j] to True for each course j that has i as a prerequisite.
    • Update the prerequisites for courses dependent on j to include the prerequisites for i.
    • Decrease the indegree for each course j and if it becomes 0, add it to the queue.
  5. Now f contains information about all direct and indirect prerequisites.
  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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:

  1. Matrix Initialization: A 2D list f of size n x n is initialized to False, where n is the number of courses. This list will keep track of prerequisite relationshipsโ€”f[i][j] being True represents that course i is a prerequisite for course j.

  2. Graph Representation: A graph g is created as a list of empty lists, where g[i] will eventually contain all the courses that directly require course i as a prerequisite. The indeg list holds the indegree of each course, which counts the number of prerequisites each course has.

  3. Building Graph and Indegree List: The prerequisites list is iterated over, and for each pair [a, b], course b is added to g[a], and the indegree of course b is incremented. This constructs the initial directed graph and the indegree list.

  4. 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.

  5. BFS Traversal:

    • While the queue is not empty, pop the front course i from the queue.
    • For each course j in g[i]:
      • Set f[i][j] to True, since i is a direct prerequisite for j.
      • Iterate over all courses h (from 0 to n-1):
        • Update f[h][j] to be the logical OR of its current value and f[h][i]. This line propagates the prerequisite information, meaning if h is a prerequisite for i and i for j, then h becomes a prerequisite for j.
      • Decrement the indegree of course j. If the indegree of j now becomes 0, it means that all its prerequisites have been accounted for, and it can be added to the queue for further processing.

  6. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example 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:

  1. Matrix Initialization: Initialize an n x n matrix f with all False, here n = 4. This will reflect that no courses are prerequisites of others to begin with.

  2. 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.

  3. Building Graph and Indegree List: The prerequisites array maybe [[0,1], [0,2], [1,3]]. From this, we populate our graph g and an indegree list indeg as follows:

    • Add course 1 to g[0] and course 2 to g[0] (because course 0 is a prerequisite for both), increment indeg[1] and indeg[2].
    • Add course 3 to g[1] (because course 1 is a prerequisite for course 3) and increment indeg[3]. After this, g would be [[1,2], [3], [], []] and indeg would be [0,1,1,1].

  4. Queue Initialization for BFS: Populate a queue q with courses that have an indegree of 0. In this case, course 0 has no prerequisites, so q = [0].

  5. BFS Traversal: Process the queue as per the algorithm:

    • Pop course 0 from q. Its prerequisites will be courses 1 and 2.
    • Mark f[0][1] and f[0][2] to True.
    • Propagate dependencies: For dependent course 1, mark f[0][3] to True (since course 0 is a prerequisite for course 1 which in turn is for course 3). Similarly, if there were courses dependent on 2, propagate the prerequisites for 0 accordingly.
    • Decrease the indegree of courses 1, 2 by 1, and any course which now has an indegree 0 is added to q. Consequently, courses 1 and 2 are added to q.
    • Continue the process for courses 1 and 2. Since course 1 has 3 as a dependent, we mark f[1][3] to True, but also f[0][3] is already True so it remains so. Now, indegree of 3 becomes 0, and it is added to q to process although 3 has no dependents.

  6. Answering Queries: For the queries, we simply check the f matrix: for the query [0, 3], we check f[0][3] which is True. For the query [2, 1], we check f[2][1] which is False. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a min heap?

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:

  1. Initialization of f and g: The two lists are initialized with sizes n x n and n, respectively. Initializations run in O(n^2) for f and O(n) for g.

  2. 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 graph g and indeg. Each operation inside the loop takes constant time, so this step runs in O(E) where E is the number of edges or prerequisites.

  3. 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's indegree becomes 0, and the for loop inside processes n possible predecessors. This results in O(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 considering n times the adjacent nodes for updating f which yields O(n * E).

  4. Answering queries: This is a direct access operation for each query in f which takes O(1) time. There may be Q queries, thus this would take O(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:

  1. Space for f: O(n^2) since it stores boolean values for every possible pair of nodes.

  2. Space for g and indeg: O(n) for each, since they store a list of adjacent nodes and indegree counts for each node, respectively.

  3. Additional space for the queue q: In the worst case, this can store all n nodes, so O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

DFS Fundamentals

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

BFS Fundamentals

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

Graph Fundamentals

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ