210. Course Schedule II

Description

Given the number of courses and a list of prerequisite pairs, determine the order in which courses should be taken to complete all courses. If it's impossible to complete all courses, return an empty array.

Intuition

This problem can be solved by performing topological sorting on a directed graph. The goal is to return a valid topological order of courses if one exists. If a cycle is detected, it means that it's impossible to complete all courses.

Approach

1. Graph Representation: - Use an adjacency list to represent the graph. - Use an array to keep track of the in-degree (number of incoming edges) for each course.
2. Topological Sorting: - Initialize a queue to store courses with no prerequisites (in-degree of zero). - Use BFS to process each course, decrementing the in-degree of connected courses. - Add courses with no remaining prerequisites to the queue.
3. Cycle Detection: - If the number of processed courses equals numCourses, all courses can be finished and the order is valid. - If not, there is a cycle in the graph, making it impossible to finish all courses.

Complexity

Time Complexity:

• Constructing the graph takes O(P) time, where P is the number of prerequisites.
• Topological sorting takes O(V + E) time, where V is the number of courses and E is the number of prerequisites.
• Total time complexity is O(V + P).

Space Complexity:

• The adjacency list takes O(V + E) space.
• The in-degree array takes O(V) space.
• The queue takes up to O(V) space.
• Total space complexity is O(V + E).

Code

C++

class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector order, inDegree(numCourses, 0);
        unordered_map> map;
        queue queue;
        
        for (auto& pre : prerequisites) {
            int target = pre[0], preCourse = pre[1];
            map[preCourse].push_back(target);
            inDegree[target] += 1;
        }
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                queue.push(i);
            }
        }
        while (!queue.empty()) {
            int node = queue.front();
            queue.pop();
            order.push_back(node);
            
            if (map.find(node) != map.end()) {
                for (int target : map[node]) {
                    inDegree[target] -= 1;
                    if (inDegree[target] == 0) {
                        queue.push(target);
                    }
                }
            }
        }
        return order.size() == numCourses ? order : vector();
    }
};

Python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        order = []
        inDegree = [0] * numCourses
        graph = {i: [] for i in range(numCourses)}
        # Initialize the graph
        for target, pre in prerequisites:
            graph[pre].append(target)
            inDegree[target] += 1
        
        # Find all courses with no prerequisites
        queue = [i for i in range(numCourses) if inDegree[i] == 0]
        
        # Process each course
        while queue:
            node = queue.pop(0)
            order.append(node)
            
            for neighbor in graph[node]:
                inDegree[neighbor] -= 1
                if inDegree[neighbor] == 0:
                    queue.append(neighbor)
        
        return order if len(order) == numCourses else []

Java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] order = new int[numCourses];
        int[] inDegree = new int[numCourses];
        Map> map = new HashMap<>();
        Queue queue = new LinkedList<>();
        // Initialize the graph
        for (int[] pre : prerequisites) {
            int target = pre[0], preCourse = pre[1];
            map.computeIfAbsent(preCourse, k -> new ArrayList<>()).add(target);
            inDegree[target] += 1;
        }
        // Find all courses with no prerequisites
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order[index++] = node;
            
            if (map.containsKey(node)) {
                for (int target : map.get(node)) {
                    inDegree[target] -= 1;
                    if (inDegree[target] == 0) {
                        queue.offer(target);
                    }
                }
            }
        }
        return index == numCourses ? order : new int[0];
    }
}

JavaScript

var findOrder = function (numCourses, prerequisites) {
    const order = [], queue = []
    const inDegree = new Array(numCourses).fill(0)
    const map = new Map()
    for (let [target, pre] of prerequisites) {
        map.has(pre) ? map.get(pre).push(target) : map.set(pre, [target])
        inDegree[target] += 1
    }
    console.log(map)
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.push(i)
        }
    }
    while (queue.length != 0) {
        let node = queue.shift()
        order.push(node)
        console.log(node, map.get(node))
        if (map.has(node)) {
            for (let tar of map.get(node)) {
                inDegree[tar] -= 1
                if (inDegree[tar] == 0) {
                    queue.push(tar)
                }
            }
        }
    }
    return order.length==numCourses?order:[]
};