Course Schedule II
Course Schedule II – Medium Level Problem
You are given an array prerequisites where each element prerequisites [i] = [a, b] specifies that course b must be completed before you can take course a.
For instance, the pair [0, 1] means you need to complete course 1 before enrolling in course 0.
The total number of courses is numCourses, labeled from 0 to numCourses – 1.
Your task is to return a valid order in which you can complete all the courses. If multiple valid orders exist, return any one of them. If it is not possible to complete all courses, return an empty array.
Examples related to Course Schedule II Problem
Example 1:
Input:
numCourses = 3, prerequisites = [[1,0]]
Output: [0,1,2]
Explanation: Ensure that course 0 is taken before course 1.
Output: [0,1,2]
Explanation: Ensure that course 0 is taken before course 1.
Example 2:
Input:
numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]
Output: [ ]
Explanation: Impossible to finish all courses.
Output: [ ]
Explanation: Impossible to finish all courses.
Constraints:
- 1 <= numCourses <= 1000
- 0 <= prerequisites.length <= 1000
- All prerequisite pairs are unique.
Hints to solve Course Schedule II Problem
Recommended Time & Space Complexity
The ideal solution should have a time complexity of O(V + E) and a space complexity of O(V + E), where V represents the number of courses (nodes), and E represents the number of prerequisites (edges).
Hint 1:
Think of this problem as a graph, where:
- Courses are the nodes.
- Each prerequisites[i] = [a, b] represents a directed edge from b to a.
Challenge is to check whether this graph contains a cycle. Why? A cycle means it is impossible to complete the courses involved in the cycle.
Can you identify an algorithm to detect cycles in a graph while also finding a valid ordering of the nodes if no cycle exists?
Hint 2:
One way to detect cycles is by using DFS (Depth First Search). While doing this, we can also find a valid course ordering.
Alternatively, use Topological Sort, which is specifically designed to determine the ordering of nodes in a Directed Acyclic Graph (DAG).
Graph must be acyclic for all courses to be completed, and each prerequisite acts as the parent of a dependent course.
Can you figure out how to implement this?
Hint 3:
To implement Topological Sort:
- Compute the indegree (number of incoming edges) for all nodes.
- Perform BFS (Breadth First Search) starting from nodes with zero indegree (indegree[node] == 0).
- For each visited node: Decrease the indegree of its neighbors (child nodes).Add child nodes with zero indegree to the queue.
- Add each visited node to the result array.
Finally, if the length of the result array matches the total number of courses, return the array.
Otherwise, return an empty array, indicating that completing all courses is impossible.
Methods to Solve Course Schedule II Problem
There are mainly 3 approaches to solve Solve Course Schedule II Problem:
- Cycle Detection (DFS)
- Topological Sort (Kahn’s Algorithm)
- Topological Sort (DFS)
1. Cycle Detection (DFS) Method
This method uses Depth First Search (DFS) to check if there is a cycle in the course dependency graph. If a cycle is detected, completing all courses is impossible; otherwise, we return the course order.
- Time complexity: O(V+E)
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector findOrder(int numCourses, vector>& prerequisites) {
unordered_map> prereq;
for (const auto& pair : prerequisites) {
prereq[pair[0]].push_back(pair[1]);
}
vector output;
unordered_set visit;
unordered_set cycle;
for (int course = 0; course < numCourses; course++) {
if (!dfs(course, prereq, visit, cycle, output)) {
return {};
}
}
return output;
}
private:
bool dfs(int course, const unordered_map>& prereq,
unordered_set& visit, unordered_set& cycle,
vector& output) {
if (cycle.count(course)) {
return false;
}
if (visit.count(course)) {
return true;
}
cycle.insert(course);
if (prereq.count(course)) {
for (int pre : prereq.at(course)) {
if (!dfs(pre, prereq, visit, cycle, output)) {
return false;
}
}
}
cycle.erase(course);
visit.insert(course);
output.push_back(course);
return true;
}
};
Java
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map> prereq = new HashMap<>();
for (int[] pair : prerequisites) {
prereq.computeIfAbsent(pair[0],
k -> new ArrayList<>()).add(pair[1]);
}
List output = new ArrayList<>();
Set visit = new HashSet<>();
Set cycle = new HashSet<>();
for (int course = 0; course < numCourses; course++) {
if (!dfs(course, prereq, visit, cycle, output)) {
return new int[0];
}
}
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
result[i] = output.get(i);
}
return result;
}
private boolean dfs(int course, Map> prereq,
Set visit, Set cycle,
List output) {
if (cycle.contains(course)) {
return false;
}
if (visit.contains(course)) {
return true;
}
cycle.add(course);
for (int pre : prereq.getOrDefault(course, Collections.emptyList())) {
if (!dfs(pre, prereq, visit, cycle, output)) {
return false;
}
}
cycle.remove(course);
visit.add(course);
output.add(course);
return true;
}
}
Python
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
prereq = {c: [] for c in range(numCourses)}
for crs, pre in prerequisites:
prereq[crs].append(pre)
output = []
visit, cycle = set(), set()
def dfs(crs):
if crs in cycle:
return False
if crs in visit:
return True
cycle.add(crs)
for pre in prereq[crs]:
if dfs(pre) == False:
return False
cycle.remove(crs)
visit.add(crs)
output.append(crs)
return True
for c in range(numCourses):
if dfs(c) == False:
return []
return output
JavaScript
class Solution {
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
findOrder(numCourses, prerequisites) {
const prereq = new Map();
for (const [course, pre] of prerequisites) {
if (!prereq.has(course)) {
prereq.set(course, []);
}
prereq.get(course).push(pre);
}
const output = [];
const visit = new Set();
const cycle = new Set();
for (let c = 0; c < numCourses; c++) {
if (!this.dfs(c, prereq, visit, cycle, output)) {
return [];
}
}
return output;
}
/**
* @param {number} course
* @param {Map} prereq
* @param {Set} visit
* @param {Set} cycle
* @param {number[]} output
* @return {boolean}
*/
dfs(course, prereq, visit, cycle, output) {
if (cycle.has(course)) {
return false;
}
if (visit.has(course)) {
return true;
}
cycle.add(course);
for (const pre of prereq.get(course) || []) {
if (!this.dfs(pre, prereq, visit, cycle, output)) {
return false;
}
}
cycle.delete(course);
visit.add(course);
output.push(course);
return true;
}
}
2. Topological Sort (Kahn’s Algorithm)
Kahn’s Algorithm is a BFS-based approach where we process nodes with zero in-degree (no prerequisites). It builds the course order step by step while detecting cycles if any nodes remain unprocessed.
- Time complexity: O(V + E)
- Space complexity: O(V + E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector findOrder(int numCourses, vector>& prerequisites) {
vector indegree(numCourses, 0);
vector> adj(numCourses);
for (auto& pre : prerequisites) {
indegree[pre[1]]++;
adj[pre[0]].push_back(pre[1]);
}
queue q;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
int finish = 0;
vector output(numCourses);
while (!q.empty()) {
int node = q.front();q.pop();
output[numCourses - finish - 1] = node;
finish++;
for (int nei : adj[node]) {
indegree[nei]--;
if (indegree[nei] == 0) {
q.push(nei);
}
}
}
if (finish != numCourses) {
return {};
}
return output;
}
};
Java
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
indegree[pre[1]]++;
adj.get(pre[0]).add(pre[1]);
}
Queue q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.add(i);
}
}
int finish = 0;
int[] output = new int[numCourses];
while (!q.isEmpty()) {
int node = q.poll();
output[numCourses - finish - 1] = node;
finish++;
for (int nei : adj.get(node)) {
indegree[nei]--;
if (indegree[nei] == 0) {
q.add(nei);
}
}
}
if (finish != numCourses) {
return new int[0];
}
return output;
}
}
Python
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
indegree = [0] * numCourses
adj = [[] for i in range(numCourses)]
for src, dst in prerequisites:
indegree[dst] += 1
adj[src].append(dst)
q = deque()
for n in range(numCourses):
if indegree[n] == 0:
q.append(n)
finish, output = 0, []
while q:
node = q.popleft()
output.append(node)
finish += 1
for nei in adj[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
if finish != numCourses:
return []
return output[::-1]
JavaScript
class Solution {
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
findOrder(numCourses, prerequisites) {
let indegree = Array(numCourses).fill(0);
let adj = Array.from({ length: numCourses }, () => []);
for (let [src, dst] of prerequisites) {
indegree[dst]++;
adj[src].push(dst);
}
let q = new Queue();
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
q.push(i);
}
}
let finish = 0;
let output = Array(numCourses);
while (!q.isEmpty()) {
let node = q.pop();
output[numCourses - finish - 1] = node;
finish++;
for (let nei of adj[node]) {
indegree[nei]--;
if (indegree[nei] === 0) {
q.push(nei);
}
}
}
if (finish !== numCourses) {
return [];
}
return output;
}
}
3. Topological Sort (DFS) Method
This method uses DFS to visit nodes in the graph, adding them to the course order in reverse as they finish processing. It ensures that prerequisites are processed first and detects cycles along the way.
- Time complexity: O(V+E)
- Space complexity: O(V+E)
Where V is the number of vertices and E is the number of edges.
Code:
C++
Java
Python
JavaScript
C++
class Solution {
vector output;
vector indegree;
vector> adj;
void dfs(int node) {
output.push_back(node);
indegree[node]--;
for (int nei : adj[node]) {
indegree[nei]--;
if (indegree[nei] == 0) {
dfs(nei);
}
}
}
public:
vector findOrder(int numCourses, vector>& prerequisites) {
adj = vector>(numCourses);
indegree = vector(numCourses, 0);
for (auto& pre : prerequisites) {
indegree[pre[0]]++;
adj[pre[1]].push_back(pre[0]);
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
dfs(i);
}
}
if (output.size() != numCourses) return {};
return output;
}
};
Java
public class Solution {
private List output = new ArrayList<>();
private int[] indegree;
private List> adj;
private void dfs(int node) {
output.add(node);
indegree[node]--;
for (int nei : adj.get(node)) {
indegree[nei]--;
if (indegree[nei] == 0) {
dfs(nei);
}
}
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
indegree = new int[numCourses];
for (int[] pre : prerequisites) {
indegree[pre[0]]++;
adj.get(pre[1]).add(pre[0]);
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
dfs(i);
}
}
if (output.size() != numCourses) return new int[0];
int[] res = new int[output.size()];
for (int i = 0; i < output.size(); i++) {
res[i] = output.get(i);
}
return res;
}
}
Python
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = [[] for i in range(numCourses)]
indegree = [0] * numCourses
for nxt, pre in prerequisites:
indegree[nxt] += 1
adj[pre].append(nxt)
output = []
def dfs(node):
output.append(node)
indegree[node] -= 1
for nei in adj[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
dfs(nei)
for i in range(numCourses):
if indegree[i] == 0:
dfs(i)
return output if len(output) == numCourses else []
JavaScript
class Solution {
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {number[]}
*/
findOrder(numCourses, prerequisites) {
let adj = Array.from({ length: numCourses }, () => []);
let indegree = Array(numCourses).fill(0);
for (let [nxt, pre] of prerequisites) {
indegree[nxt]++;
adj[pre].push(nxt);
}
let output = [];
const dfs = (node) => {
output.push(node);
indegree[node]--;
for (let nei of adj[node]) {
indegree[nei]--;
if (indegree[nei] === 0) {
dfs(nei);
}
}
};
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
dfs(i);
}
}
return output.length === numCourses ? output : [];
}
}
