Skip to main content

207. Course Schedule

mediumAsked at Pinterest

Course Schedule is Pinterest's go-to cycle-detection problem: given course prerequisites as edges, decide whether you can finish every course. The interviewer wants a topological sort or DFS three-color cycle check — pick one and execute it cleanly.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest SWE onsite reports list Course Schedule as the graph round, often paired with Course Schedule II.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

Problem

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

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= a_i, b_i < numCourses
  • All pairs 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: 0 needs 1, 1 needs 0.

Approaches

1. Kahn's algorithm (BFS topological sort, optimal)

Compute in-degree per node. Push every zero-in-degree node into a queue. Pop, decrement neighbors' in-degree, push new zeros. If processed count equals numCourses, no 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] += 1;
  }
  const q = [];
  for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
  let processed = 0;
  while (q.length) {
    const u = q.shift();
    processed += 1;
    for (const v of graph[u]) {
      indeg[v] -= 1;
      if (indeg[v] === 0) q.push(v);
    }
  }
  return processed === numCourses;
}

Tradeoff: Iterative, easy to reason about, no recursion-depth risk. Standard answer at Pinterest. Edge: q.shift() is O(n) — for very large graphs use a head pointer.

2. DFS three-color cycle detection

Track each node's state: 0 = unvisited, 1 = in current DFS path, 2 = fully processed. If DFS hits a 1-marked node, cycle.

Time
O(V + E)
Space
O(V + E)
function canFinishDfs(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[a].push(b);
  const state = new Array(numCourses).fill(0); // 0=white, 1=gray, 2=black
  function dfs(u) {
    if (state[u] === 1) return false; // cycle
    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: Slightly shorter to write, but recursion-depth bites on long chains (2000 courses is fine in V8; longer DAGs need an iterative DFS). The three-color invariant is the part to narrate.

Pinterest-specific tips

Pinterest interviewers grade on whether you reach for the topological-sort frame immediately when you see 'prerequisites.' Lead with Kahn's because it's iterative and queue-based — easier to extend to the LeetCode 210 follow-up (return the actual order, not just the boolean). Mention DFS three-color as 'I could also do this with DFS using a gray/black state' to signal you know both.

Common mistakes

  • Building the graph in the wrong direction — prereqs[i] = [a, b] means b -> a (you take b before a), so b is the parent in the topo-sort.
  • Marking nodes as 'visited' instead of three-color in the DFS version — visited alone can't distinguish 'in this path' from 'fully done', so cycles are missed.
  • Forgetting disconnected components — every node needs an entry point, not just those reachable from node 0.
  • Returning the wrong sentinel when the BFS finishes: processed === numCourses, not q.length === 0.

Follow-up questions

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

  • Course Schedule II (LeetCode 210): return the actual order, not just feasibility.
  • Alien Dictionary (LeetCode 269): topo-sort with implicit edges from word ordering.
  • Detect ALL cycles, not just whether one exists.
  • Streaming: prerequisites arrive online — maintain feasibility with each addition.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Should I use BFS or DFS?

Either passes correctness. BFS (Kahn's) is the safer default at Pinterest because it generalizes naturally to the order-returning follow-up. DFS three-color is more concise but recursion-heavy.

Why does Pinterest specifically ask this?

Many Pinterest infra problems reduce to dependency ordering — build systems, data pipelines, board feature dependencies. Topo-sort is the primitive that surfaces repeatedly.

Free learning resources

Curated free links for this problem.

More Pinterest coding interview questions

See all Pinterest problems →

Companies that also ask Course Schedule