210. Course Schedule II

At a Glance

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

Problem (one-liner)

Return one valid order to take all numCourses given prerequisite pairs bi → ai (must take bi before ai), or [] if impossible (cycle).

Recognition Cues

Same as 207 but need actual order (Kahn or DFS postorder reversed)

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

Kahn — pop indegree 0, append to order — O(V+E).
DFS — postorder on reversed graph or three-color + build reverse of finish order— O(V+E).

Optimal Solution

Go

func findOrder(numCourses int, prerequisites [][]int) []int {
	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)
		}
	}
	order := make([]int, 0, numCourses)
	head := 0
	for head < len(queue) {
		current := queue[head]
		head++
		order = append(order, current)
		for _, neighbor := range adjacency[current] {
			indegree[neighbor]--
			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}
	if len(order) != numCourses {
		return []int{}
	}
	return order
}

JavaScript

function findOrder(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);
    }
  }
  const order = [];
  let head = 0;
  while (head < queue.length) {
    const current = queue[head];
    head += 1;
    order.push(current);
    for (const neighbor of adjacency[current]) {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  if (order.length !== numCourses) {
    return [];
  }
  return order;
}

Walkthrough

Kahn queue drains all indegree-zero nodes; order length short iff cycle.

Invariant: Any node still with positive indegree after process lies on a directed cycle or unreachable sink component.

Edge Cases

Linear chain — unique order modulo compatible swaps
Empty prereqs — any permutation works; Kahn may output 0,1,2,...

Pitfalls

Same edge direction mistake as 207

Variants

Multiple valid orders — Kahn can emit different sequences; verify lexical smallest if asked.
Detect cycle and print edge — combine with union-find or DFS edge classification.

Mind-Map Tags

#topological-sort #kahn #ordering #bfs-level #course-plan