Skip to main content

18. Course Schedule

mediumAsked at Roblox

Detect cycles in a directed prerequisite graph to determine if all courses can be finished — Roblox applies the same topological-sort logic to resolve asset-loading dependency chains in its streaming engine.

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

Problem

There are numCourses courses labeled 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 otherwise (i.e., no cycle exists).

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • All prerequisite pairs are unique

Examples

Example 1

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

Explanation: Take course 0 then course 1.

Example 2

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

Explanation: Cycle: 0 requires 1, 1 requires 0.

Approaches

1. Brute force — DFS with visited set per start node

For each node, run DFS tracking the current path to detect back edges. Resets path tracking per source, causing redundant work.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[b].push(a);

  const UNVISITED = 0, VISITING = 1, VISITED = 2;
  const state = new Array(numCourses).fill(UNVISITED);

  function hasCycle(node) {
    if (state[node] === VISITING) return true;
    if (state[node] === VISITED) return false;
    state[node] = VISITING;
    for (const next of graph[node]) {
      if (hasCycle(next)) return true;
    }
    state[node] = VISITED;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff:

2. Optimal — Kahn's BFS topological sort

Compute in-degrees, enqueue zero-in-degree nodes, and peel off layers. If all nodes are processed, no cycle exists. Avoids recursion depth issues.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    inDegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  let processed = 0;
  while (queue.length) {
    const node = queue.shift();
    processed++;
    for (const next of graph[node]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }

  return processed === numCourses;
}

Tradeoff:

Roblox-specific tips

Roblox cares about cycle detection in dependency graphs because circular asset dependencies can deadlock the streaming loader. Interviewers want to see you distinguish DFS three-color marking (good for detecting cycles early) from Kahn's BFS (good for producing a valid load order). Know both; explain the tradeoff in terms of stack depth vs. queue memory for graphs with thousands of asset nodes.

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

Practice these live with InterviewChamp.AI →