Course Schedule II

---

Course Schedule II: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given 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.

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].

---

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

---

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• a_i != b_i
• All the pairs [a_i, b_i] are distinct.

---

Try this Problem on your own or check similar problems:

1. Course Schedule
2. Minimum Height Trees
3. Build a Matrix With Conditions

Solution:

Java

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new List[numCourses];
    int[] degree = new int[numCourses];

    for(int i = 0; i < graph.length; ++i){
        graph[i] = new ArrayList<>();
    }

    for(int[] p: prerequisites){
        graph[p[1]].add(p[0]);
        ++degree[p[0]];
    }

    Queue<Integer> q = new LinkedList<>();

    for(int i = 0; i < degree.length; ++i){
        if(degree[i] == 0) q.add(i);
    }

    List<Integer> result = new ArrayList<>();

    while(!q.isEmpty()){
        int node = q.poll();
        result.add(node);
        for(int neighbour: graph[node]){
            if(--degree[neighbour] == 0) q.add(neighbour);
        }
    }

    return result.size() == numCourses ? result.stream().mapToInt(i -> i).toArray() : new int[]{};
}

JavaScript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(0).map(() => []);
  const degree = new Array(numCourses).fill(0);

  for (const [course, prerequisite] of prerequisites) {
    graph[prerequisite].push(course);
    degree[course]++;
  }

  const queue = [];
  for (let i = 0; i < degree.length; i++) {
    if (degree[i] === 0) {
      queue.push(i);
    }
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (--degree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return result.length === numCourses ? result : [];
};

Python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(numCourses)]
        degree = [0] * numCourses

        for prerequisite in prerequisites:
            graph[prerequisite[1]].append(prerequisite[0])
            degree[prerequisite[0]] += 1

        queue = deque()
        for i in range(len(degree)):
            if degree[i] == 0:
                queue.append(i)

        result = []
        while queue:
            node = queue.popleft()
            result.append(node)
            for neighbor in graph[node]:
                degree[neighbor] -= 1
                if degree[neighbor] == 0:
                    queue.append(neighbor)

        return result if len(result) == numCourses else []

C++

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> degree(numCourses);

        for (const auto& prerequisite : prerequisites) {
            graph[prerequisite[1]].push_back(prerequisite[0]);
            degree[prerequisite[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < degree.size(); i++) {
            if (degree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> result;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            result.push_back(node);

            for (int neighbor : graph[node]) {
                degree[neighbor]--;
                if (degree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return result.size() == numCourses ? result : vector<int>();
    }
};

---

Time/Space Complexity:

• Time Complexity: O(E+V) where E number of edges and V number of vertices
• Space Complexity: O(V)

---

Explanation:

We reuse the same topological sort implementation (which is the natural order of courses we have to take to finish all of them) in Course Schedule, this time only storing the nodes in a result list which we finally transform to array and return as final result. We have the same time and space complexity as in the previous solution.