Skip to main content

88. Course Schedule

mediumAsked at Ola

Decide if all courses can be finished given prerequisite pairs (cycle detection).

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

Problem

There are numCourses courses labeled 0 to numCourses-1, with prerequisites given as pairs [a, b] meaning to take a you must first take b. Return true if you can finish all courses, otherwise false.

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. DFS coloring

Recurse with three node states (unseen, in-stack, done) and reject if you reach an in-stack node.

Time
O(V+E)
Space
O(V+E)
// 3-color DFS; identical big-O but adds recursion depth concerns

Tradeoff:

2. Kahn's algorithm (BFS topo)

Compute indegrees; start with 0-indegree nodes; pop and decrement neighbors. Cycle present if not all nodes processed.

Time
O(V+E)
Space
O(V+E)
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 done = 0;
  while (q.length) {
    const v = q.shift(); done++;
    for (const n of graph[v]) if (--indeg[n] === 0) q.push(n);
  }
  return done === numCourses;
}

Tradeoff:

Ola-specific tips

Ola interviewers like Kahn's clarity; tie it to validating prerequisite dependencies in a driver-onboarding training plan graph.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →