Skip to main content

207. Course Schedule

mediumAsked at Broadcom

Determine if you can finish all courses given prerequisite dependencies — a cycle detection problem on a directed graph. Broadcom asks this because dependency-cycle detection is foundational to firmware build-system validation and hardware-block initialization ordering in complex SoC boot sequences.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-12)— Cited in Broadcom SWE onsite feedback as a directed-graph cycle-detection problem.
  • Blind (2025-10)— Broadcom infrastructure threads list Course Schedule alongside Number of Islands as top graph problems to prepare.

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses, otherwise, return false.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Examples

Example 1

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

Explanation: Take course 0 then course 1. No cycle.

Example 2

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

Explanation: Courses 0 and 1 are mutually dependent — cycle detected.

Approaches

1. DFS with 3-color cycle detection

Mark each node as 0 (unvisited), 1 (in current DFS path), or 2 (fully processed). A back edge to a node marked 1 indicates a cycle. If DFS completes without finding a back edge, return true.

Time
O(V + E)
Space
O(V + E)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const state = new Array(numCourses).fill(0); // 0=unvisited, 1=visiting, 2=done
  function hasCycle(node) {
    if (state[node] === 1) return true;  // back edge
    if (state[node] === 2) return false; // already processed
    state[node] = 1;
    for (const neighbor of adj[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
  }
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Tradeoff: O(V+E). The 3-color trick is elegant but requires careful state management. DFS stack depth can be O(V) in a chain-shaped graph.

2. Topological sort via BFS (Kahn's algorithm)

Compute in-degrees. Enqueue all nodes with in-degree 0. Process each, reducing neighbor in-degrees. If all nodes are processed, no cycle exists.

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

Tradeoff: O(V+E). Iterative — no recursion stack risk. Kahn's algorithm is preferred in embedded or compiler contexts because it naturally produces a topological order, not just a cycle boolean.

Broadcom-specific tips

Broadcom interviewers value knowing both approaches: 'DFS with 3-coloring detects cycles; BFS with Kahn's also produces the topological order, which is useful if you need to sequence hardware-block initialisation.' In SoC firmware, boot-sequence ordering is exactly a topological sort over hardware dependency graphs. Mention this connection. If asked which is better, say: 'Kahn's is safer in production because it's iterative.'

Common mistakes

  • Confusing the edge direction — prerequisites[i] = [a, b] means b → a, so b is a prerequisite of a.
  • In the DFS version, not resetting state[node] to 2 after fully processing it — causes false cycle reports.
  • In Kahn's, not initialising in-degrees for all nodes including those with no edges.
  • Returning false when processed < numCourses without checking — any unprocessed node means a cycle exists.

Follow-up questions

An interviewer at Broadcom may pivot to one of these next:

  • Course Schedule II (LC 210) — return the actual topological order.
  • How would you handle a dynamic graph where prerequisites are added or removed at runtime?
  • How does this relate to deadlock detection in distributed systems?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does Kahn's algorithm detect cycles?

Nodes in a cycle never reach in-degree 0 during processing. If processed < numCourses at the end, at least one cycle exists.

What is the 3-color DFS state machine?

0=not yet visited, 1=currently being explored (in the DFS stack), 2=fully explored and verified cycle-free. A back edge to a node in state 1 is the cycle indicator.

How does Broadcom use topological sort in practice?

SoC firmware must initialise hardware blocks in dependency order. A misconfigured init sequence is equivalent to a prerequisite cycle — the system hangs. Topological sort validates the configuration at compile time.

Practice these live with InterviewChamp.AI

Drill Course Schedule and other Broadcom interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →