Course Schedule Ii - Leetcode Solution

Problem Statement:

You are given a list of n courses, labeled from 0 to n-1. You are also given a list of prerequisite pairs [[a1, b1], [a2, b2], ..., [am, bm]] where each pair denotes that the course b[i] must be taken before the course a[i]. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

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.

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,1,2,3]. Another correct ordering is [0,2,1,3].

Solution:

This problem is a variation of the Topological Sorting problem. In this problem, we need to find the ordering of the courses to complete all of them by following the given prerequisite pairs. If there is no such ordering possible, we return an empty array.

In order to solve this problem, we first construct the graph using the given prerequisite pairs. We maintain an incoming edge count for each node in the graph to keep track of the number of prerequisite courses that needs to be completed before a course can be taken.

We use a queue to maintain a list of nodes with incoming edge count = 0. We add all the nodes with incoming edge count = 0 to the queue initially.

We start a while loop until the queue is not empty. In each iteration of the loop, we remove a node from the queue and add it to the result list. We then decrement the incoming edge count of all the nodes that are adjacent to this node. If the incoming edge count of any adjacent node becomes 0, we add that node to the queue.

After the while loop, if the size of the result list is equal to the total number of nodes in the graph, it means we have found a valid ordering of courses. Otherwise, we return an empty array.

Below is the Python implementation of the above solution.

from collections import defaultdict, deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Construct the graph
        graph = defaultdict(list)
        incoming_edges = [0] * numCourses
        
        for u, v in prerequisites:
            graph[v].append(u)
            incoming_edges[u] += 1
            
        # Add nodes with incoming edge count = 0 to the queue
        queue = deque([])
        for i in range(numCourses):
            if incoming_edges[i] == 0:
                queue.append(i)
                
        result = []
        while queue:
            node = queue.popleft()
            result.append(node)
            
            for adjacent_node in graph[node]:
                incoming_edges[adjacent_node] -= 1
                
                if incoming_edges[adjacent_node] == 0:
                    queue.append(adjacent_node)
                    
        if len(result) != numCourses:
            return []
        
        return result

Time Complexity: O(V+E), where V is the total number of nodes (courses) and E is the total number of edges (prerequisite pairs) in the graph.

Space Complexity: O(V+E), where V is the total number of nodes (courses) and E is the total number of edges (prerequisite pairs) in the graph, as we are storing the graph using a defaultdict and incoming edge counts using a list.

1