Link

Medium Topological Sort DFS BFS

Amazon

Apple

Bytedance

Facebook

Google

Microsoft

Oracle

2020-05-29

207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Question:

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:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5

Solution:

Store each course with its in node number and outnode list. Using BFS topological sort to find if we can visit all the nodes.

Time: O(V+E)
Space: O(V+E)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) return true;
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int[] counter = new int[numCourses];
        Queue<Integer> que = new LinkedList<>();
        int result = 0;
        
        for (int[] i : prerequisites) {
            int from = i[1];
            int to = i[0];
            List<Integer> curr = map.getOrDefault(from, new ArrayList<>());
            curr.add(to);
            map.put(from, curr);
            counter[to]++;          
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (counter[i] == 0) {
                que.add(i);
            }
        }
        
        while (!que.isEmpty()) {
            int curr = que.poll();
            result++;
            if (map.containsKey(curr)) {
                for (int i : map.get(curr)) {
                    counter[i]--;
                    if (counter[i] == 0) {
                        que.add(i);
                    }
                }
            }
        }
        return result == numCourses;
    }
}