algoadvance

You are given a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0, 1].

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are multiple valid orderings, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,2,1,3].

Constraints:

• The input prerequisites are provided in no particular order.
• numCourses will be a positive integer.
• The prerequisite pairs are presented as a 2D array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi before course ai.

Clarifying Questions:

1. Can there be multiple valid course sequences or is there a unique one?
   • There can be multiple valid sequences.
2. Is the input always valid, i.e., always representing a Directed Acyclic Graph (DAG)?
   • Input can represent cycles which need to be detected, and in such cases, we should return an empty array.
3. Do we need to check if the course numbers are within the valid range (0 to numCourses-1)?
   • Assume all course numbers are valid.

Strategy:

To solve this problem, we’ll use Kahn’s Algorithm for Topological Sorting of a Directed Acyclic Graph (DAG). The main steps are:

1. Initialize the Graph and In-Degree Array:
   • Create an adjacency list to represent the courses and their prerequisites.
   • Create an array to keep track of the in-degrees (number of prerequisites) of each course.
2. Populate the Graph and In-Degree Array:
   • For each pair [a, b] in prerequisites, add an edge from b to a in the adjacency list and increment the in-degree of a.
3. Find Courses with No Prerequisites:
   • Initialize a queue with all courses that have in-degree of 0 (no prerequisites).
4. Process the Courses:
   • While the queue is not empty, perform the following:
     • Dequeue a course from the queue.
     • Add it to the result list.
     • For each neighbor (course dependent on the dequeued course), decrement its in-degree.
     • If any neighbor’s in-degree becomes 0, add it to the queue.
5. Check for Cycles:
   • If all courses are processed (total number of courses in the result list equals numCourses), then return the result list.
   • Otherwise, return an empty list indicating that it is impossible to finish all courses (due to the presence of a cycle).

Code:

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    # Step 1: Initialize graph & in-degree array
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    # Step 2: Populate graph and in-degree array
    for course, pre in prerequisites:
        graph[pre].append(course)
        in_degree[course] += 1
    
    # Step 3: Find courses with no prerequisites
    queue = deque(course for course in range(numCourses) if in_degree[course] == 0)
    order = []
    
    # Step 4: Process courses
    while queue:
        course = queue.popleft()
        order.append(course)
        
        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Step 5: Check for cycles
    if len(order) == numCourses:
        return order
    else:
        return []

# Example usage:
print(findOrder(2, [[1, 0]]))  # Output: [0, 1]
print(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # Output: [0, 2, 1, 3] (or any valid order)

Time Complexity:

• Building the graph & in-degree array: O(P), where P is the number of prerequisite pairs.
• Queue initialization & processing nodes: O(V + E), where V is the number of courses and E is the number of edges (prerequisites).
• Hence, the overall time complexity is O(V + E).

This solution is efficient for the given problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?