Problem
There are a total of n courses you have to take, labeled from 0 to n-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?
Example 1:
Input: 2, [[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: 2, [[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.
Note:
- 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.
Solution
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function(numCourses, prerequisites) {
var edges = Array(numCourses).fill(0).map(_ => Array(numCourses).fill(0));
var incoming = Array(numCourses).fill(0);
var len = prerequisites.length;
var post = 0;
var prev = 0;
var queue = [];
var num = 0;
var count = 0;
for (var i = 0; i < len; i++) {
prev = prerequisites[i][1];
post = prerequisites[i][0];
if (edges[prev][post] === 0) {
incoming[post]++;
edges[prev][post] = 1;
}
}
for (var j = 0; j < numCourses; j++) {
if (incoming[j] === 0) queue.push(j);
}
while (queue.length) {
count++;
num = queue.pop()
for (var k = 0; k < numCourses; k++) {
if (edges[num][k] === 1 && --incoming[k] === 0) queue.push(k);
}
}
return count === numCourses;
};
Explain:
nope.
Complexity:
- Time complexity : O(n^2).
- Space complexity : O(n^2).