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

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

• Prerequisites / ordering constraints
• Cycle detection vs topo ordering count

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

• 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

Similar Problems

• 210. Course Schedule II — return a valid topo order
• 269. Alien Dictionary — topo on characters (harder)
• 802. Find Eventual Safe States — graph coloring / terminal nodes

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