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).

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

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

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

Similar Problems

• 207. Course Schedule — boolean feasibility, same edge direction
• 269. Alien Dictionary — topo output as letters
• 329. Longest Increasing Path in a Matrix — DAG DP after implicit edges

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