17. Course Schedule

mediumAsked at Electronic Arts

Detect a cycle in a directed graph of course prerequisites, a pattern EA applies to dependency graphs in asset loading and game-state initialization systems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

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

Examples

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Output

true

Example 2

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

false

Approaches

1. DFS cycle detection with colors

Use 3-color marking (unvisited, in-progress, done) to detect back edges indicating cycles.

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);
  function dfs(u) {
    if (state[u] === 1) return false;
    if (state[u] === 2) return true;
    state[u] = 1;
    for (const v of adj[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:

2. Topological sort (Kahn's BFS)

Build in-degree counts and process zero-in-degree nodes in a queue (BFS). If all nodes are processed, no cycle exists. EA interviewers often prefer this iterative approach for clarity in dependency resolution problems.

Time: O(V+E)
Space: O(V+E)

function canFinish(numCourses, prerequisites) {
  const inDeg = new Array(numCourses).fill(0);
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a, b] of prerequisites) { adj[b].push(a); inDeg[a]++; }
  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++;
    for (const v of adj[u]) if (--inDeg[v] === 0) q.push(v);
  }
  return processed === numCourses;
}

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →