Skip to main content

15. Course Schedule

mediumAsked at Byju's

Decide whether a set of prerequisite-linked courses can all be finished.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given a prerequisites array where prerequisites[i] = [ai, bi] means you must take bi before ai. Return true if you can finish all courses; otherwise return false. This is equivalent to detecting a cycle in a directed graph.

Constraints

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

Examples

Example 1

Input
numCourses = 2, prerequisites = [[1,0]]
Output
true

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Approaches

1. Naive cycle search

For each course, DFS its dependencies and look for repeats with a per-start visited set.

Time
O(V * (V+E))
Space
O(V+E)
function canFinish(n, prereqs){
  const adj=Array.from({length:n},()=>[]);
  for(const [a,b] of prereqs) adj[a].push(b);
  for(let i=0;i<n;i++){const stack=[i],seen=new Set();while(stack.length){const x=stack.pop();if(seen.has(x))return false;seen.add(x);for(const nb of adj[x]) if(nb===i)return false; else stack.push(nb);}}
  return true;
}

Tradeoff:

2. Kahn topo sort

Compute in-degrees, push zero-indegree nodes onto a queue, and process them while decrementing neighbors. If every course gets processed, the graph is acyclic.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const indeg = new Array(numCourses).fill(0);
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let taken = 0;
  while (q.length) {
    const c = q.shift(); taken++;
    for (const next of adj[c]) if (--indeg[next] === 0) q.push(next);
  }
  return taken === numCourses;
}

Tradeoff:

Byju's-specific tips

Byju's K-12 curriculum is a prerequisite DAG, so explicitly call out that connection to recommendation-engine interviewers.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Course Schedule and other Byju's interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →