Skip to main content

16. Course Schedule

mediumAsked at Brex

Detect a cycle in a directed graph of course prerequisites — directly mirrors approval-chain and spend-policy dependency validation at Brex.

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

Problem

There are numCourses courses labeled 0 to numCourses-1. Given a list of prerequisite pairs [ai, bi] meaning you must take bi before ai, determine if it is possible to finish all courses.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 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 visited coloring

Mark nodes gray (in progress) and black (done); a gray-to-gray edge indicates a cycle.

Time
O(V+E)
Space
O(V+E)
// Build adjacency list, then DFS with state[0=unvisited, 1=visiting, 2=done]
// If we reach a node with state=1, cycle detected → return false

Tradeoff:

2. Topological sort (Kahn's BFS)

Compute in-degrees, enqueue zero-in-degree nodes, process and decrement neighbors. If all nodes are processed the graph is acyclic.

Time
O(V+E)
Space
O(V+E)
function canFinish(numCourses, prerequisites) {
  const inDeg = new Array(numCourses).fill(0);
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) { adj[b].push(a); inDeg[a]++; }
  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) queue.push(i);
  let processed = 0;
  while (queue.length) {
    const node = queue.shift(); processed++;
    for (const nb of adj[node]) { if (--inDeg[nb] === 0) queue.push(nb); }
  }
  return processed === numCourses;
}

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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

Practice these live with InterviewChamp.AI →