Skip to main content

207. Course Schedule

mediumAsked at Uber

Given courses and prerequisites, determine if you can finish all courses (is the prerequisite graph a DAG?). Uber asks this to test whether you reach for Kahn's BFS topological sort or DFS cycle detection.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4 onsite reports list Course Schedule as a recurring graph medium.
  • Blind (2025-11)— Recurring in Uber backend interview reports.

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: 1 needs 0, 0 needs 1.

Approaches

1. DFS cycle detection (3-color)

DFS from each unvisited node. Mark gray on entry, black on exit. A gray node hit during DFS is a back edge -> 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[b].push(a);
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numCourses).fill(WHITE);
  function dfs(u) {
    color[u] = GRAY;
    for (const v of graph[u]) {
      if (color[v] === GRAY) return false;
      if (color[v] === WHITE && !dfs(v)) return false;
    }
    color[u] = BLACK;
    return true;
  }
  for (let i = 0; i < numCourses; i++) if (color[i] === WHITE && !dfs(i)) return false;
  return true;
}

Tradeoff: Classic 3-color cycle detection. Recursion depth can hit numCourses; not a concern at this size but worth flagging.

2. Kahn's BFS topological sort (optimal)

Compute in-degrees. Queue all nodes with in-degree 0. Pop, decrement neighbors, queue any that drop to 0. If you process all nodes, 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]++; }
  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 recursion stack risk. Same asymptotic complexity. Often the cleanest answer to whiteboard.

Uber-specific tips

Uber interviewers want you to model the problem as graph + cycle check explicitly. Say: 'Prerequisites define directed edges. Finishing all courses = topological order exists = the graph is a DAG = no cycle.' That mapping is what's being graded; the choice of DFS or BFS comes second.

Common mistakes

  • Confusing edge direction: prerequisites[i] = [a, b] means b is a prereq for a, so the edge is b -> a (not a -> b).
  • DFS without the 3-color trick — using just 'visited' can't distinguish a back edge from a cross edge in a DAG.
  • Forgetting to start DFS from every node — disconnected courses still need processing.

Follow-up questions

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

  • Course Schedule II (LC 210) — return the actual order, not just feasibility.
  • Detect cycles in undirected graphs — Union-Find or DFS-with-parent.
  • Course Schedule IV (LC 1462) — transitive closure queries.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

DFS or BFS — which does Uber prefer?

Both score equally. Kahn's BFS is more naturally framed as a topological sort; DFS 3-color is a classic cycle-detection idiom. Pick whichever you can write bug-free.

Why edge direction prereq -> course?

Topological-sort convention: edges point from 'must come first' to 'comes after'. Course Schedule II returns nodes in topological order, which is the order you'd take the classes.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →