Skip to main content

207. Course Schedule

mediumAsked at Shopify

Course Schedule is Shopify's dependency-graph round. Real motivations: 'can the install order for these app packages succeed?' or 'do these merchant onboarding steps cycle?'. The interviewer wants topological sort or cycle detection by DFS.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend onsites cite Course Schedule as a recurring graph-traversal question.
  • Reddit r/cscareerquestions (2025-10)— Shopify new-grad reports include the LeetCode 210 follow-up (return the ordering).

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] = [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 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: 0 -> 1 -> 0.

Approaches

1. Brute-force ordering check (try permutations)

Generate possible orderings and check if any satisfies all prerequisites.

Time
O(n!)
Space
O(n)
// Don't ship this. Factorial blow-up at n = 2000 is unfathomable.
// Included only to motivate the graph-based approach.

Tradeoff: Factorial. Not even a realistic option; mention only to anchor 'we need a graph algorithm'.

2. Topological sort (Kahn's BFS)

Build adjacency list + in-degree array. Push all in-degree-0 nodes onto a queue. Pop nodes, decrement neighbors' in-degrees, push when they hit 0. If processed count equals numCourses, no cycle.

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 taken = 0;
  while (queue.length) {
    const c = queue.shift();
    taken++;
    for (const next of adj[c]) {
      if (--inDegree[next] === 0) queue.push(next);
    }
  }
  return taken === numCourses;
}

Tradeoff: Iterative, no recursion. Maps directly to the real-world mental model: 'process every prerequisite-free course, then process whatever became prerequisite-free, and so on.' Shopify's preferred answer for new-grad candidates.

3. DFS cycle detection (white/gray/black)

DFS each unvisited node. Mark gray (in stack) on enter, black (done) on exit. Hitting a gray neighbor = cycle.

Time
O(V + E)
Space
O(V + E)
function canFinishDFS(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) adj[b].push(a);
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  function dfs(node) {
    if (color[node] === GRAY) return false; // cycle
    if (color[node] === BLACK) return true;
    color[node] = GRAY;
    for (const next of adj[node]) {
      if (!dfs(next)) return false;
    }
    color[node] = BLACK;
    return true;
  }
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }
  return true;
}

Tradeoff: Same complexity, recursive. The white/gray/black coloring is the clean cycle-detection pattern. Risk: deep recursion on a 2000-node chain can stack-overflow some engines; for the interview, BFS is the safer default.

Shopify-specific tips

Shopify will probably extend to LeetCode 210 (return the actual ordering, not just true/false). Be ready: Kahn's BFS gives you the order for free — just collect nodes as you pop. The DFS variant gives reverse postorder. Volunteer this extension before being asked.

Common mistakes

  • Edge direction confusion: prerequisites[i] = [a, b] means b -> a (must do b BEFORE a). Many candidates flip this.
  • Forgetting that not every node has prerequisites — isolated nodes have in-degree 0 and should be on the initial queue.
  • Using a visited Set in DFS instead of three-state coloring — a Set can't distinguish 'currently being processed' from 'fully done', so you'll miss cycles.
  • Quadratic adjacency build via adj.find(...) — use a length-numCourses array of arrays.

Follow-up questions

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

  • Return the actual order (LeetCode 210).
  • Course Schedule III (LeetCode 630) — greedy + heap, courses have durations and deadlines.
  • Alien Dictionary (LeetCode 269) — derive letter ordering from a sorted word list.
  • Detect a cycle in an undirected graph (Union-Find or DFS with parent tracking).
  • What if prerequisites can be 'AND/OR' (some courses unlock if you take any of several)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

BFS vs DFS — which does Shopify prefer?

BFS (Kahn's). It maps to the real-world mental model and avoids the deep-recursion risk. DFS is acceptable if you use the three-color marking and explicitly call out the cycle-detection invariant.

Can you do it without building the adjacency list?

Not efficiently. The adjacency list is O(V + E) memory, which is the minimum for any algorithm that touches every edge. Skipping the list and re-scanning prerequisites per step would be O(V * E).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →