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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Course Schedule II

Difficulty: Medium

Problem Description

You are given a total of numCourses courses labeled from 0 to numCourses - 1. You have an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Key Insights

  • The problem can be modeled as a directed graph where courses are nodes and prerequisites are directed edges.
  • A valid course order can be determined using topological sorting.
  • If a cycle is detected in the graph, it indicates that it's impossible to complete all courses.
  • Both Depth-First Search (DFS) and Kahn's algorithm (BFS) can be used to perform topological sorting.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges).
Space Complexity: O(V + E) for storing the graph and additional structures like in-degrees or visitation status.

Solution

To solve the problem, we can use topological sorting to determine a valid order of courses. The graph is represented using an adjacency list, and we also maintain an array to track the in-degree of each course. We can use Kahn's algorithm (BFS approach) where we start from courses with zero in-degrees and build the order iteratively.

  1. Build the graph using an adjacency list from the prerequisites.
  2. Create an array to store the in-degrees of each course.
  3. Initialize a queue with all courses that have zero in-degrees.
  4. Repeatedly remove courses from the queue, adding them to the course order, and reduce the in-degrees of their neighbors.
  5. If a neighbor's in-degree drops to zero, add it to the queue.
  6. If the number of courses in the order equals numCourses, return the order. Otherwise, return an empty array.

Code Solutions

from collections import deque

def findOrder(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    
    # Build the graph and in-degree array
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Queue for courses with no prerequisites
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        
        # Reduce the in-degree of neighboring courses
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if we were able to include all courses
    return order if len(order) == numCourses else []
← Back to All Questions