Skip to main content

71. Course Schedule

mediumAsked at Salesforce

Determine if all courses can be finished given prerequisite pairs (cycle detection in a directed graph). Salesforce uses this directly in their workflow-rule cycle detection.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses topological sort in workflow-rule chain validation.
  • Blind (2025-11)— Salesforce L4/L5 onsite favorite.

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

Example 2

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

Explanation: Cycle.

Approaches

1. DFS with colored visited

0 = unvisited, 1 = in current path, 2 = done. If DFS re-enters a 1-node, cycle.

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);
  function dfs(u) {
    if (state[u] === 1) return false;
    if (state[u] === 2) return true;
    state[u] = 1;
    for (const v of graph[u]) if (!dfs(v)) return false;
    state[u] = 2;
    return true;
  }
  for (let i = 0; i < numCourses; i++) if (!dfs(i)) return false;
  return true;
}

Tradeoff: Three-color (white/gray/black) DFS is the textbook cycle detection.

2. Kahn's algorithm (BFS topo sort)

Compute in-degrees. Queue nodes with in-degree 0. Pop, decrement neighbors' in-degree, enqueue zeros. Count processed; if < n, cycle.

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

Tradeoff: Iterative, no stack overflow risk. Kahn's is preferred for production. Salesforce uses this exact pattern.

Salesforce-specific tips

Salesforce uses topological sort directly in workflow-rule chain validation (you can't have rule A trigger B trigger A). They grade on whether you can name BOTH algorithms — DFS-colored AND Kahn's — and explain the trade-off. Bonus signal: extend to LC 210 which returns the actual order.

Common mistakes

  • Confusing the edge direction — [a, b] means b is prereq for a, so edge b → a.
  • Using a single boolean 'visited' instead of three colors — can't detect cycles within a path.
  • Not initializing the queue with ALL zero-indegree nodes — partial start misses some courses.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the order.
  • Course Schedule III (LC 630) — scheduling with deadlines.
  • Detect cycle in undirected graph (Union-Find or DFS with parent tracking).

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 three colors instead of two?

Two colors (visited / unvisited) can't tell us 'this node is on the current DFS path' (gray) vs 'fully explored, no cycle from here' (black). The distinction is essential for cycle detection.

Kahn's or DFS-colored?

Kahn's is iterative (safer for huge graphs). DFS is more compact. Both are O(V+E). Salesforce prefers Kahn's for production reliability.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →