Skip to main content

16. Course Schedule

mediumAsked at GitLab

Decide whether a set of courses with prerequisite pairs can be completed — i.e. whether the dependency graph is acyclic.

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

Problem

Given numCourses and a list of prerequisite pairs [a, b] meaning b must be taken before a, return true if you can finish all courses. Equivalent to detecting a cycle in a directed graph.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • All pairs are unique

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 with three colors

Mark nodes white/gray/black; revisiting a gray node means a cycle.

Time
O(V+E)
Space
O(V+E)
const g=Array.from({length:n},()=>[]);
for (const [a,b] of pre) g[b].push(a);
const col=new Array(n).fill(0);
const dfs=u=>{ if (col[u]===1) return false; if (col[u]===2) return true;
  col[u]=1; for (const v of g[u]) if (!dfs(v)) return false;
  col[u]=2; return true; };
for (let i=0;i<n;i++) if (!dfs(i)) return false;
return true;

Tradeoff:

2. Kahn's BFS topological sort

Compute in-degrees, repeatedly pop zero-in-degree nodes, decrement neighbors. If we processed all nodes, the graph is a DAG.

Time
O(V+E)
Space
O(V+E)
function canFinish(n, pre){
  const g = Array.from({length:n}, () => []);
  const inDeg = new Array(n).fill(0);
  for (const [a, b] of pre){ g[b].push(a); inDeg[a]++; }
  const q = [];
  for (let i = 0; i < n; i++) if (inDeg[i] === 0) q.push(i);
  let done = 0;
  while (q.length){
    const u = q.shift();
    done++;
    for (const v of g[u]) if (--inDeg[v] === 0) q.push(v);
  }
  return done === n;
}

Tradeoff:

GitLab-specific tips

GitLab maps this directly to their CI-graph topological sort — pipeline `needs:` declarations form a DAG and any cycle must be flagged before a runner picks up a job.

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

Practice these live with InterviewChamp.AI →