207. Course Schedule

At a Glance

Topic: graphs
Pattern: Topological Sort
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Apple
Frequency: Very High
LeetCode: 207

Problem (one-liner)

numCourses labeled 0..n-1; prerequisites as directed edges b → a (a depends on b). Return whether you can finish all courses (graph is a DAG — no directed cycles).

Recognition Cues

Prerequisites / ordering constraints
Cycle detection vs topo ordering count

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

DFS three-color — gray/black recursion stack — O(V+E).
Kahn BFS — indegree queue — O(V+E) — either is optimal.

Optimal Solution

Go

func canFinish(numCourses int, prerequisites [][]int) bool {
	adjacency := make([][]int, numCourses)
	indegree := make([]int, numCourses)
	for _, edge := range prerequisites {
		course := edge[0]
		prerequisite := edge[1]
		adjacency[prerequisite] = append(adjacency[prerequisite], course)
		indegree[course]++
	}
	queue := make([]int, 0)
	for course := 0; course < numCourses; course++ {
		if indegree[course] == 0 {
			queue = append(queue, course)
		}
	}
	taken := 0
	head := 0
	for head < len(queue) {
		current := queue[head]
		head++
		taken++
		for _, neighbor := range adjacency[current] {
			indegree[neighbor]--
			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	return taken == numCourses
}

JavaScript

function canFinish(numCourses, prerequisites) {
  const adjacency = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const edge of prerequisites) {
    const course = edge[0];
    const prerequisite = edge[1];
    adjacency[prerequisite].push(course);
    indegree[course] += 1;
  }
  const queue = [];
  for (let course = 0; course < numCourses; course += 1) {
    if (indegree[course] === 0) {
      queue.push(course);
    }
  }
  let taken = 0;
  while (queue.length > 0) {
    const current = queue.shift();
    taken += 1;
    for (const neighbor of adjacency[current]) {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  return taken === numCourses;
}

Walkthrough

Indegree 0 courses enter queue; each dequeue drains dependents; if cycle exists, some indegree never hits zero.

Invariant: Processed count equals numCourses iff DAG.

Edge Cases

No prerequisites — trivial order
Disjoint chains

Pitfalls

Reversed edge orientation — LeetCode [ai, bi] means take bi before ai, so edge bi → ai (code maps prerequisite → course)
Reversed edge orientation breaks topo order and cycle checks

Variants

Edge list as prerequisites reversed — normalize direction before coding.
Longest path in DAG — after topo, relax edges in order.

Mind-Map Tags

#topological-sort #kahn #dfs-cycle #directed-graph #prerequisites