18. Course Schedule

mediumAsked at DigitalOcean

Detect a cycle in a directed dependency graph using topological sort — directly analogous to circular dependency detection in infrastructure automation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

There are numCourses courses (0 to numCourses-1). You are given an array prerequisites where prerequisites[i] = [ai, bi] means you must take course bi before course ai. Return true if you can finish all courses, false if there is a circular dependency.

Constraints

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

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 color marking (naive set)

Maintain visited and inStack sets; cycle exists if we revisit an in-stack node.

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

function canFinish(n, prereqs) {
  const graph = Array.from({length:n}, ()=>[]);
  for (const [a,b] of prereqs) graph[b].push(a);
  const visited = new Set(), inStack = new Set();
  function dfs(u) {
    if (inStack.has(u)) return false;
    if (visited.has(u)) return true;
    inStack.add(u); visited.add(u);
    for (const v of graph[u]) if (!dfs(v)) return false;
    inStack.delete(u);
    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; enqueue nodes with in-degree 0; process them and decrement neighbors. If we process all nodes, no cycle exists.

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

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

Tradeoff:

DigitalOcean-specific tips

DigitalOcean interviewers love this problem because Terraform's dependency graph uses the same cycle-detection algorithm — mentioning that connection earns bonus signal.

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

Practice these live with InterviewChamp.AI →