Medium Topological Sort DFS BFS
Amazon
Apple
Bytedance
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;
}
}