207. Course Schedule
mediumAsked at HubSpotHubSpot asks Course Schedule to assess cycle detection in directed graphs — a pattern that arises in their workflow automation engine where circular dependency detection between triggers and actions is a critical correctness guarantee.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in HubSpot loops.
- Glassdoor (2026-Q1)— HubSpot SWE candidates report Course Schedule appearing in onsite rounds focused on graph algorithms.
- r/cscareerquestions (2025-09)— HubSpot interview prep threads cite Course Schedule as an occasional graph-cycle detection problem.
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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]]trueExplanation: Take course 0 first, then course 1. No cycle.
Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseExplanation: To take course 1 you need course 0, and to take course 0 you need course 1 — a cycle.
Approaches
1. Topological sort via Kahn's algorithm (BFS)
Build an adjacency list and compute in-degrees for all nodes. Enqueue all zero-in-degree nodes. Process: dequeue, decrement neighbors' in-degrees, enqueue new zeros. If all nodes are processed, no cycle exists.
- 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;
let head = 0;
while (head < queue.length) {
const node = queue[head++];
processed++;
for (const neighbor of graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return processed === numCourses;
}Tradeoff: O(V+E) time and space. Kahn's algorithm is iterative and avoids deep recursion. The key insight: if a cycle exists, at least one node will never reach in-degree 0 and will not be processed. If processed === numCourses, no cycle exists.
2. DFS cycle detection (3-color)
For each unvisited node, run DFS using three states: unvisited (0), in-progress (1), done (2). If DFS reaches a node currently in-progress, a cycle exists.
- 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 state = new Array(numCourses).fill(0); // 0=unvisited,1=in-progress,2=done
function hasCycle(node) {
if (state[node] === 1) return true; // back edge
if (state[node] === 2) return false; // already cleared
state[node] = 1;
for (const neighbor of graph[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: Same complexity. The 3-color approach is intuitive for detecting back edges (cycles) in DFS. Kahn's BFS is preferred when the interviewer asks for iterative code or topological order output.
HubSpot-specific tips
Reframe the problem before coding: 'This is asking whether the directed prerequisite graph is a DAG — detectable via topological sort or DFS cycle detection.' HubSpot interviewers value the reframing step. Both approaches are acceptable; Kahn's BFS is often preferred because it's iterative and also produces a valid topological order as a bonus. Connect it to real systems: 'This is exactly how dependency resolvers and workflow engines check for circular dependencies.'
Common mistakes
- Building the graph in the wrong direction — graph[b].push(a) means 'b must come before a', not the other way around.
- Forgetting to check processed === numCourses at the end — checking queue emptiness misses nodes never enqueued due to cycles.
- Using only 2 states in DFS (visited/unvisited) — can't distinguish back edges from already-finished nodes; 3 colors are necessary.
- Not initializing in-degrees before building the graph — partial initialization leads to incorrect zero-degree detection.
Follow-up questions
An interviewer at HubSpot may pivot to one of these next:
- Course Schedule II (LC 210) — return the actual topological order if it exists.
- Minimum Height Trees (LC 310) — find roots of minimum-height trees in an undirected graph.
- How would you detect cycles in an undirected graph? (Union-Find or DFS with parent tracking.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
What does 'in-degree' mean?
The in-degree of a node is the number of edges directed into it. A zero in-degree node has no prerequisites and can be taken immediately.
Why does 'processed === numCourses' detect no cycle?
In a cycle, every node in the cycle has at least one unresolved prerequisite (from another cycle node), so its in-degree never reaches 0 and it's never processed. If all nodes are processed, the graph is acyclic.
Can this problem have self-loops?
The problem says all pairs are unique and bi ≠ ai (implied), but a self-loop would mean course i requires itself — a cycle of length 1. Both algorithms handle it correctly: in-degree of i is never decremented to 0 in Kahn's; DFS finds the back edge immediately.
Practice these live with InterviewChamp.AI
Drill Course Schedule and other HubSpot interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →