Check if it is possible to finish all task from given dependencies (Course Schedule I) | Problems

Given numCourses and prerequisite pairs, determine if it is possible to finish all courses (i.e., detect if the dependency graph has a cycle).

Example: numCourses = 2, prerequisites = [[1,0]] → Output: true

Sample Input

—

Sample Output

—

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000

Test Cases

Case 1

Args: [2,[[1,0]]] Expected: true

Case 2

Args: [2,[[1,0],[0,1]]] Expected: false

Topics

Graph BFS DFS

Topological Sort (Kahn's Algorithm)

If we can process all courses via BFS topological sort, there's no cycle.

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({length: numCourses}, () => []);
  const inDeg = Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { graph[b].push(a); inDeg[a]++; }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) q.push(i);
  let count = 0;
  while (q.length) {
    const node = q.shift(); count++;
    for (const next of graph[node]) { if (--inDeg[next] === 0) q.push(next); }
  }
  return count === numCourses;
}

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

Saved in this browser only. Private to you.