Skip to main content

22. Course Schedule

mediumAsked at Squarespace

Detect whether prerequisite dependencies allow all courses to be completed; Squarespace uses it to test cycle detection in a directed graph.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. Given an array prerequisites where prerequisites[i] = [a, b] means you must take b before a, return true if you can finish all courses.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2

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 full revisits

DFS from every node and look for back edges, but without memoization this explodes on chains.

Time
O(V * (V+E))
Space
O(V+E)
// build adj; for each course, DFS along edges tracking a path-stack;
// if you revisit a node already on the stack, return false.

Tradeoff:

2. Kahn's algorithm topological sort

Compute in-degrees, repeatedly remove zero-in-degree nodes, and check that you removed every node.

Time
O(V+E)
Space
O(V+E)
function canFinish(n, prereqs) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [a, b] of prereqs) { adj[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 adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return done === n;
}

Tradeoff:

Squarespace-specific tips

Squarespace likes a callout that topological ordering is exactly what their template-publish pipeline uses to render parent sections before child blocks.

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

Practice these live with InterviewChamp.AI →