Taro Logo

Course Schedule IV

#876 Most AskedMedium
7 views
Topics:
Graphs

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.

  • For example, the pair [0, 1] indicates that you have to take course 0 before you can take course 1.

Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.

You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.

Return a boolean array answer, where answer[j] is the answer to the jth query.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: 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]
Explanation: 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]

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on the number of courses `n`, and the number of prerequisites in `prerequisites` and the number of queries in `queries`? Should I be concerned about memory usage with very large inputs?
  2. Are there any cycles in the prerequisite graph? If so, how should I handle them (e.g., is it guaranteed that the input will always be a valid directed acyclic graph (DAG)?)
  3. Can a prerequisite for a course be the course itself (e.g., `[0,0]` in `prerequisites`)? If so, should I consider a course to be a prerequisite for itself?
  4. If a query `[a, b]` represents whether course `a` is a prerequisite of course `b`, is it possible for `a` and `b` to be the same course? If so, should I return `true` or `false`?
  5. Is the input `prerequisites` guaranteed to have valid course numbers (i.e., are the course numbers always within the range `0` to `n-1`)? What should I return if there are invalid course numbers in the input?

Brute Force Solution

Approach

For each question about whether one class is a prerequisite for another, the brute force approach explores every possible path between the two classes to see if a path exists. This means considering all possible combinations of classes to check if one leads to the other. It's like manually checking every possible route on a map to see if you can get from point A to point B.

Here's how the algorithm would work step-by-step:

  1. For each question, start by listing all possible courses that could be taken.
  2. Then, using the prerequisite rules, see if you can get from the first course in the question to the second course by taking one course at a time.
  3. Try every possible combination of courses in between the two courses to see if there is a valid path.
  4. If after checking all possible course combinations, you find at least one path, then the first course is a prerequisite for the second.
  5. If you cannot find any valid path after checking every combination of courses, then the first course is not a prerequisite for the second.
  6. Repeat this entire process for each question about course prerequisites.

Code Implementation

def course_schedule_brute_force(number_of_courses, prerequisites, queries):
    results = []
    for query in queries:
        course_a = query[0]
        course_b = query[1]
        
        if can_take_course(number_of_courses, prerequisites, course_a, course_b):
            results.append(True)
        else:
            results.append(False)
    return results

def can_take_course(number_of_courses, prerequisites, course_a, course_b):
    # Use a recursive depth-first search to find a path
    return has_path(prerequisites, course_a, course_b, set())

def has_path(prerequisites, current_course, target_course, visited):
    if current_course == target_course:
        return True

    if current_course in visited:
        return False

    visited.add(current_course)
    
    # Iterate through prerequisites to explore neighbors.
    for prerequisite, course in prerequisites:
        if prerequisite == current_course:

            # Recursively search for path to target
            if has_path(prerequisites, course, target_course, visited):
                return True

    # Mark as unvisited for other paths.
    visited.remove(current_course)

    # If no path found, return false
    return False

Big(O) Analysis

Time Complexity
O(n^(n+2))For each of the q queries, the brute-force approach explores all possible paths between two courses. In the worst case, to determine if course A is a prerequisite for course B, we might need to check every possible combination of courses in between. If there are n courses in total, for each of q queries, we might have to check up to n courses in each potential path of length up to n. Building each path could take up to n steps, so we have n^n paths to check, times n for creating the paths, multiplied by the q queries, results in O(q * n^(n+1)). However, since the path existence check itself can be O(n), the total worst case is O(q * n^(n+2)). In the worst-case q is proportional to n so the time complexity approaches O(n^(n+2)).
Space Complexity
O(N!)The brute force approach explores every possible combination of courses. In the worst case, for each question, we might need to store a list of all possible courses, leading to a list of size N. The number of combinations to check can grow factorially with the number of courses (N!). The algorithm implicitly stores these combinations either in a list or through recursive calls to explore each possible path between courses, resulting in a space complexity proportional to the number of combinations explored. Therefore, the auxiliary space is O(N!).

Optimal Solution

Approach

The problem asks us to determine if one course is a prerequisite of another. We can efficiently solve this by pre-computing all possible prerequisite relationships using a technique similar to finding the shortest path between all pairs of courses, and then answering queries based on this pre-computed information.

Here's how the algorithm would work step-by-step:

  1. First, represent the courses and their prerequisites as a network where courses are points and prerequisites are links.
  2. Then, find out which courses can reach each other in the network, meaning which courses are prerequisites for which other courses.
  3. A good method for finding all reachable courses is to repeatedly go through the network. At each course, mark down all other courses that this course leads to directly or indirectly.
  4. Once you know which courses can reach which other courses, you can quickly answer whether a course is a prerequisite of another course by just looking up if there is a path between them in our pre-computed relationships.
  5. Specifically, if course A can reach course B, that means A is a prerequisite of B.
  6. Repeat the last step for all the queries you're asked.

Code Implementation

def course_schedule_iv(number_of_courses, prerequisites, queries):
    adjacency_list = [[] for _ in range(number_of_courses)]
    for source, destination in prerequisites:
        adjacency_list[source].append(destination)

    reachable = [[False] * number_of_courses for _ in range(number_of_courses)]

    # Iterate over all courses to find reachable nodes.
    for start_course in range(number_of_courses):
        visited = [False] * number_of_courses
        queue = [start_course]
        visited[start_course] = True

        while queue:
            current_course = queue.pop(0)
            reachable[start_course][current_course] = True

            for neighbor in adjacency_list[current_course]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

    result = []
    # Evaluate each query to determine prerequisite relationship.
    for course_a, course_b in queries:
        result.append(reachable[course_a][course_b])

    return result

Big(O) Analysis

Time Complexity
O(n^2 + q)The algorithm first constructs an adjacency list representing the course prerequisites, which takes O(n) time, where n is the number of courses. Finding all reachable courses from each course involves iterating through the adjacency list for each course. In the worst case, this transitive closure computation using a nested loop structure takes O(n^2) time, where n is the number of courses. After pre-computing the reachability, answering each query requires a simple lookup in the pre-computed data structure, taking O(1) time per query. With q queries, this step takes O(q) time. Therefore, the overall time complexity is O(n^2 + q).
Space Complexity
O(N^2)The algorithm pre-computes all possible prerequisite relationships between courses. This is typically done using a data structure like an adjacency matrix or a boolean matrix called reachable, where reachable[i][j] is true if course i is a prerequisite of course j. This matrix requires N^2 space, where N is the number of courses. Therefore the space grows quadratically with the number of courses. Other auxiliary variables used have constant space and do not affect the asymptotic space complexity.

Edge Cases

Empty prerequisites list
How to Handle:
Return a list of 'true' values, indicating all queries are reachable since no prerequisites exist.
Empty queries list
How to Handle:
Return an empty list as there are no queries to evaluate.
Course dependency cycle exists
How to Handle:
The topological sort should detect cycles and return an empty ordering, resulting in all queries being 'false'.
Queries involving non-existent courses (out of bounds)
How to Handle:
Treat non-existent courses as unreachable, resulting in a 'false' result for those queries.
Maximum number of courses (n is large) and prerequisites (array length large)
How to Handle:
Ensure the graph representation and transitive closure algorithm are space and time efficient (e.g., using adjacency list and optimized DFS or Floyd-Warshall).
All courses depend on the first course
How to Handle:
The transitive closure will correctly identify reachability from the first course to all others.
All courses are independent (no prerequisites)
How to Handle:
The transitive closure matrix will have 'true' only on the diagonal, representing reachability from a course to itself.
Large number of queries
How to Handle:
Precompute the transitive closure for efficiency; answering each query then becomes an O(1) lookup.
0/1114 completed