Course Schedule

Course Schedule: 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 true if you can finish all courses. Otherwise, return false.

Example 1:

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

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0,
and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public boolean canFinish(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);
    }

    int count = 0;

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

    return count == numCourses;
}

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = 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);
    }
  }

  let count = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    count++;

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

  return count === numCourses;
};

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        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)

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

        return count == numCourses

class Solution {
public:
    bool canFinish(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);
            }
        }

        int count = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            count++;

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

        return count == numCourses;
    }
};

Time/Space Complexity:

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

Explanation:

Whenever you have a clear relation between different elements given by the problem statement you should think if you can reframe the initial problem to a graph problem. In our case the elements are courses, and the obvious relations are given by prerequisites. We can only finish all courses if there are no cycles in the graph (second example, you can't start course 0 before you start 1, but you can't start course 1 before you start 0 so it's impossible to finish the course since if modeled courses as a graph we would have a cycle). To find if graph contains cycle we perform topological sort: Topological sort of directed graph is a linear ordering of its vertices such that, for every directed edge U -> V from vertex U to vertex V, U comes before V in the ordering. Why does topological sort detect cycle in graph? In Topological Sort, the idea is to visit the parent node followed by the child node. If the given graph contains a cycle, then there is at least one node which is a parent as well as a child thus breaking topological order. So, if we can visit all elements count == numCourses we know there is an existing topological order, otherwise if there is a cycle topological order would break and we wouldn't have visited all elements.

So how do we perform topological sort:

We represent the graph in adjacency-list representation (each node mapped to its neighbor), also we track the degree of a node (number of incoming edges to each node)
We use prerequisites array to form the adjacency-lists and increase the degree for each node
Next, a queue is created with initial candidates picked so they have degree == 0 (course that can start without waiting for completion of any other course)
Each time we poll another course from the queue of candidates we check its neighbors and if there are any potential candidates after we have visited the current node which we can be added to the queue (--degree[neighbour] == 0)

For space complexity we have O(E+V) since we're building a graph of E edges and V vertices. Since we visit all edges and vertices in the topological sort we have O(V+E) time complexity.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​