We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Course Schedule IV

Number: 1558

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Uber

Problem Description

Determine if a course is a prerequisite for another given a list of courses and their direct prerequisites. Prerequisites can be indirect; that is, if course A is required for B and B is required for C, then A is required for C. For each query, answer whether one course is a prerequisite for another.

Key Insights

  • Represent courses and prerequisites as a directed acyclic graph (DAG).
  • Use graph traversal techniques (DFS or BFS) or compute the transitive closure.
  • The Floyd Warshall algorithm can precompute reachability between all courses.
  • After precomputation, each query can be answered in constant time by checking the reachability matrix.

Space and Time Complexity

Time Complexity: O(N^3 + Q) where N = numCourses (Floyd Warshall algorithm) and Q = number of queries
Space Complexity: O(N^2) for storing the reachability matrix

Solution

We solve the problem by converting it into computing reachability in a DAG. The approach is to use the Floyd Warshall algorithm to compute a transitive closure.
Steps:

  1. Build a boolean reachability matrix and mark direct prerequisites.
  2. Use a triple-nested loop (Floyd Warshall) to update the matrix such that if course i can reach course k and course k can reach course j, then course i can reach course j.
  3. Answer each query in constant time by checking the precomputed reachability matrix.

Code Solutions

# Python solution using Floyd Warshall algorithm
def check_prerequisites(numCourses, prerequisites, queries):
    # Create a 2D reachability matrix initialized to False
    reachable = [[False] * numCourses for _ in range(numCourses)]
    
    # Set direct prerequisites in the matrix
    for pre, course in prerequisites:
        reachable[pre][course] = True
    
    # Compute transitive closure with Floyd Warshall algorithm
    for k in range(numCourses):
        for i in range(numCourses):
            if reachable[i][k]:
                for j in range(numCourses):
                    if reachable[k][j]:
                        reachable[i][j] = True
    
    # Process each query and return the results
    return [reachable[u][v] for u, v in queries]

# Example usage:
numCourses = 3
prerequisites = [[1,2],[1,0],[2,0]]
queries = [[1,0],[1,2]]
print(check_prerequisites(numCourses, prerequisites, queries))  # Expected output: [True, True]
← Back to All Questions