Breadth-first and depth-first search are two skeletons that between them solve most of the graph problems in an interview loop. Each section below takes one canonical variant, explains what single knob it turns on the base skeleton, and shows the same implementation in Python, C++, Rust, TypeScript, Go, and Swift. The tabs remember your language across snippets and visits. Every function is lifted verbatim from a repository where it runs against the official LeetCode examples plus the edge cases that actually get submissions rejected, so the code on this page is the code that passed.
The BFS skeleton never changes: seed a queue, mark nodes visited as they are enqueued, then pop, expand, and push until empty. The variants change exactly one thing each, namely what seeds the queue, what counts as an edge, or what the queue itself is. DFS variants turn two different knobs: what marking means, whether a permanent flag, a three-state color, or a temporary mark that gets undone, and where the answer is computed, on the way down or combined on the way back up.
- Level-order traversal
- Single-source grid BFS
- Multi-source BFS
- Bidirectional BFS
- Topological sort, Kahn's algorithm
- 0-1 BFS
- Flood fill and connected components
- Iterative DFS with an explicit stack
- Cycle detection with three colors
- Topological sort by finish times
- Postorder tree DFS with return values
- Backtracking on a grid
1. Level-order traversal
LC 102 · Binary Tree Level Order Traversal · the BFS entry point
Level-order traversal is the cleanest place to watch the queue work, because a tree has no cycles and the visited set disappears entirely. The one trick is to snapshot the queue length before draining each round: by the BFS invariant the queue only ever holds nodes at two consecutive depths, so everything in it at that instant is exactly one level. Popping that many nodes and pushing their children walks the tree one depth at a time in O(n) time and O(width) space.
The same round-by-round drain reappears in zigzag traversal, right side view, minimum depth, and every simulation that advances in waves, including Rotting Oranges below.
Memory hook: Size snapshot = level boundary.
def level_order(root: Optional[TreeNode]) -> list[list[int]]:
"""LC 102. Binary Tree Level Order Traversal.
Knob: snapshot len(queue) before each round so one while-iteration
consumes exactly one level. O(n) time, O(width) space.
"""
if not root:
return []
ans: list[list[int]] = []
queue = deque([root])
while queue:
level: list[int] = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(level)
return ans
// LC 102. Snapshot the queue size so each while-round consumes one level.
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = static_cast<int>(q.size());
vector<int> level;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(level);
}
return ans;
}
/// LC 102. Snapshot the queue length so each while-round consumes one level.
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
let mut queue = VecDeque::new();
if let Some(node) = root {
queue.push_back(node);
}
while !queue.is_empty() {
let level_size = queue.len();
let mut level = Vec::with_capacity(level_size);
for _ in 0..level_size {
let node = queue.pop_front().unwrap();
let node = node.borrow();
level.push(node.val);
if let Some(left) = &node.left {
queue.push_back(Rc::clone(left));
}
if let Some(right) = &node.right {
queue.push_back(Rc::clone(right));
}
}
ans.push(level);
}
ans
}
/** LC 102. Snapshot the queue length so each while-round consumes one level. */
export function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
const ans: number[][] = [];
let queue: TreeNode[] = [root];
while (queue.length > 0) {
const next: TreeNode[] = [];
const level: number[] = [];
for (const node of queue) {
level.push(node.val);
if (node.left) next.push(node.left);
if (node.right) next.push(node.right);
}
ans.push(level);
queue = next; // swap whole levels instead of shifting one by one
}
return ans;
}
// LC 102. Snapshot the queue length so each while-round consumes one level.
func levelOrder(root *TreeNode) [][]int {
ans := [][]int{}
if root == nil {
return ans
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
level := make([]int, 0, levelSize)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
ans = append(ans, level)
}
return ans
}
// LC 102. Snapshot the queue count so each while-round consumes one level.
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else { return [] }
var ans: [[Int]] = []
var queue: [TreeNode] = [root]
var head = 0
while head < queue.count {
let levelEnd = queue.count
var level: [Int] = []
while head < levelEnd {
let node = queue[head]
head += 1
level.append(node.val)
if let left = node.left { queue.append(left) }
if let right = node.right { queue.append(right) }
}
ans.append(level)
}
return ans
}
2. Single-source grid BFS
LC 1091 · Shortest Path in Binary Matrix
The grid itself is the graph. Instead of building an adjacency list, you enumerate the eight direction offsets, bounds-check, and skip blocked or already-seen cells; that neighbor function is the entire edge set. The detail that decides correctness is marking a cell visited the moment it is enqueued rather than when it is dequeued. Late marking lets the same cell enter the queue many times, which inflates the queue on large grids and breaks the distance guarantee. Time and space are O(n²), one enqueue per cell.
Once nodes are states and edges are moves, the same code solves mazes, knight paths, and Open the Lock, where the cells are lock combinations and the directions are wheel turns.
Memory hook: The grid is the graph; directions are the edges.
def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
"""LC 1091. Shortest Path in Binary Matrix.
Single-source BFS on a grid, 8 directions, path length counted in
cells. Visited is marked the moment a cell is enqueued -- marking on
dequeue lets the same cell enter the queue many times and breaks the
distance guarantee. O(n^2) time and space.
"""
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance in cells)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
while queue:
r, c, dist = queue.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] == 0:
seen[nr][nc] = True
queue.append((nr, nc, dist + 1))
return -1
// LC 1091. Single-source grid BFS, 8 directions. Mark visited ON ENQUEUE.
int shortestPathBinaryMatrix(vector<vector<int>> grid) {
int n = static_cast<int>(grid.size());
if (grid[0][0] || grid[n - 1][n - 1]) return -1;
queue<array<int, 3>> q; // row, col, distance in cells
vector<vector<bool>> seen(n, vector<bool>(n, false));
q.push({0, 0, 1});
seen[0][0] = true;
while (!q.empty()) {
auto [r, c, dist] = q.front();
q.pop();
if (r == n - 1 && c == n - 1) return dist;
for (int dr = -1; dr <= 1; ++dr)
for (int dc = -1; dc <= 1; ++dc) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] == 0) {
seen[nr][nc] = true;
q.push({nr, nc, dist + 1});
}
}
}
return -1;
}
/// LC 1091. Single-source grid BFS, 8 directions. Mark visited ON ENQUEUE.
pub fn shortest_path_binary_matrix(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
if grid[0][0] != 0 || grid[n - 1][n - 1] != 0 {
return -1;
}
let mut seen = vec![vec![false; n]; n];
let mut queue = VecDeque::new();
queue.push_back((0usize, 0usize, 1i32));
seen[0][0] = true;
while let Some((r, c, dist)) = queue.pop_front() {
if r == n - 1 && c == n - 1 {
return dist;
}
for dr in -1i64..=1 {
for dc in -1i64..=1 {
let (nr, nc) = (r as i64 + dr, c as i64 + dc);
if nr >= 0 && nr < n as i64 && nc >= 0 && nc < n as i64 {
let (nr, nc) = (nr as usize, nc as usize);
if !seen[nr][nc] && grid[nr][nc] == 0 {
seen[nr][nc] = true;
queue.push_back((nr, nc, dist + 1));
}
}
}
}
}
-1
}
/** LC 1091. Single-source grid BFS, 8 directions. Mark visited ON ENQUEUE. */
export function shortestPathBinaryMatrix(grid: number[][]): number {
const n = grid.length;
if (grid[0][0] !== 0 || grid[n - 1][n - 1] !== 0) return -1;
const queue: [number, number, number][] = [[0, 0, 1]]; // row, col, distance
const seen: boolean[][] = Array.from({ length: n }, () => new Array<boolean>(n).fill(false));
seen[0][0] = true;
let head = 0; // O(1) dequeue without shift()
while (head < queue.length) {
const [r, c, dist] = queue[head++];
if (r === n - 1 && c === n - 1) return dist;
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] === 0) {
seen[nr][nc] = true;
queue.push([nr, nc, dist + 1]);
}
}
}
}
return -1;
}
// LC 1091. Single-source grid BFS, 8 directions. Mark visited ON ENQUEUE.
func shortestPathBinaryMatrix(grid [][]int) int {
n := len(grid)
if grid[0][0] != 0 || grid[n-1][n-1] != 0 {
return -1
}
queue := [][3]int{{0, 0, 1}} // row, col, distance in cells
seen := make([][]bool, n)
for r := range seen {
seen[r] = make([]bool, n)
}
seen[0][0] = true
for len(queue) > 0 {
r, c, dist := queue[0][0], queue[0][1], queue[0][2]
queue = queue[1:]
if r == n-1 && c == n-1 {
return dist
}
for dr := -1; dr <= 1; dr++ {
for dc := -1; dc <= 1; dc++ {
nr, nc := r+dr, c+dc
if nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] == 0 {
seen[nr][nc] = true
queue = append(queue, [3]int{nr, nc, dist + 1})
}
}
}
}
return -1
}
// LC 1091. Single-source grid BFS, 8 directions. Mark visited ON ENQUEUE.
func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
let n = grid.count
if grid[0][0] == 1 || grid[n - 1][n - 1] == 1 { return -1 }
var queue: [(Int, Int, Int)] = [(0, 0, 1)] // row, col, distance in cells
var head = 0
var seen = Array(repeating: Array(repeating: false, count: n), count: n)
seen[0][0] = true
while head < queue.count {
let (r, c, dist) = queue[head]
head += 1
if r == n - 1 && c == n - 1 { return dist }
for dr in -1...1 {
for dc in -1...1 {
let nr = r + dr, nc = c + dc
if nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc] && grid[nr][nc] == 0 {
seen[nr][nc] = true
queue.append((nr, nc, dist + 1))
}
}
}
}
return -1
}
3. Multi-source BFS
LC 994 · Rotting Oranges
One changed line turns single-source BFS into a different tool: seed the queue with every rotten orange before the loop starts. All the wavefronts then advance together, so each fresh orange is reached at the earliest minute any source could reach it, and each completed round of the queue is one minute of simulated time. Conceptually you have added a virtual super-source connected to every seed at distance zero. O(mn) time and space.
Whenever a question asks for the distance to the nearest of many sources, Walls and Gates and 01 Matrix included, seed them all and run one pass instead of one search per cell.
Memory hook: Many sources, one queue.
def oranges_rotting(grid: list[list[int]]) -> int:
"""LC 994. Rotting Oranges.
Multi-source BFS: seed the queue with EVERY rotten orange at minute 0,
then expand in level-sized rounds. The wavefronts from all sources
advance together, so each fresh orange is reached at the earliest
possible minute. O(mn) time and space.
"""
rows, cols = len(grid), len(grid[0])
queue: deque[tuple[int, int]] = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh:
for _ in range(len(queue)):
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return -1 if fresh else minutes
// LC 994. Multi-source BFS: seed every rotten orange, expand in rounds.
int orangesRotting(vector<vector<int>> grid) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
queue<pair<int, int>> q;
int fresh = 0;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) {
if (grid[r][c] == 2) q.push({r, c});
else if (grid[r][c] == 1) ++fresh;
}
int minutes = 0;
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!q.empty() && fresh > 0) {
int roundSize = static_cast<int>(q.size());
for (int i = 0; i < roundSize; ++i) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
--fresh;
q.push({nr, nc});
}
}
}
++minutes;
}
return fresh ? -1 : minutes;
}
/// LC 994. Multi-source BFS: seed every rotten orange, expand in rounds.
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
let (rows, cols) = (grid.len(), grid[0].len());
let mut queue = VecDeque::new();
let mut fresh = 0;
for r in 0..rows {
for c in 0..cols {
match grid[r][c] {
2 => queue.push_back((r, c)),
1 => fresh += 1,
_ => {}
}
}
}
let mut minutes = 0;
while !queue.is_empty() && fresh > 0 {
for _ in 0..queue.len() {
let (r, c) = queue.pop_front().unwrap();
for (nr, nc) in [(r.wrapping_sub(1), c), (r + 1, c), (r, c.wrapping_sub(1)), (r, c + 1)] {
if nr < rows && nc < cols && grid[nr][nc] == 1 {
grid[nr][nc] = 2;
fresh -= 1;
queue.push_back((nr, nc));
}
}
}
minutes += 1;
}
if fresh > 0 { -1 } else { minutes }
}
const FOUR_DIRECTIONS: ReadonlyArray<readonly [number, number]> = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
/** LC 994. Multi-source BFS: seed every rotten orange, expand in rounds. */
export function orangesRotting(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
let queue: [number, number][] = [];
let fresh = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
let minutes = 0;
while (queue.length > 0 && fresh > 0) {
const next: [number, number][] = [];
for (const [r, c] of queue) {
for (const [dr, dc] of FOUR_DIRECTIONS) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
next.push([nr, nc]);
}
}
}
queue = next;
minutes++;
}
return fresh > 0 ? -1 : minutes;
}
// LC 994. Multi-source BFS: seed every rotten orange, expand in rounds.
func orangesRotting(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
queue := [][2]int{}
fresh := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == 2 {
queue = append(queue, [2]int{r, c})
} else if grid[r][c] == 1 {
fresh++
}
}
}
minutes := 0
dr := [4]int{1, -1, 0, 0}
dc := [4]int{0, 0, 1, -1}
for len(queue) > 0 && fresh > 0 {
roundSize := len(queue)
for i := 0; i < roundSize; i++ {
r, c := queue[0][0], queue[0][1]
queue = queue[1:]
for d := 0; d < 4; d++ {
nr, nc := r+dr[d], c+dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
grid[nr][nc] = 2
fresh--
queue = append(queue, [2]int{nr, nc})
}
}
}
minutes++
}
if fresh > 0 {
return -1
}
return minutes
}
// LC 994. Multi-source BFS: seed every rotten orange, expand in rounds.
func orangesRotting(_ grid: [[Int]]) -> Int {
var grid = grid
let rows = grid.count, cols = grid[0].count
var queue: [(Int, Int)] = []
var head = 0
var fresh = 0
for r in 0..<rows {
for c in 0..<cols {
if grid[r][c] == 2 {
queue.append((r, c))
} else if grid[r][c] == 1 {
fresh += 1
}
}
}
var minutes = 0
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
while head < queue.count && fresh > 0 {
let roundEnd = queue.count
while head < roundEnd {
let (r, c) = queue[head]
head += 1
for d in 0..<4 {
let nr = r + dr[d], nc = c + dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
}
}
}
minutes += 1
}
return fresh > 0 ? -1 : minutes
}
4. Bidirectional BFS
LC 127 · Word Ladder
Words are nodes and one-letter edits are edges, and the graph never gets built; neighbors are generated by substituting each letter at each position and testing membership in the dictionary set. Searching from both ends and always expanding the smaller frontier turns roughly b^d work into roughly 2·b^(d/2): the two waves meet in the middle, and the moment a generated candidate appears in the opposite frontier the answer is the current distance plus one. Removing a word from the pool doubles as the visited mark.
Minimum Genetic Mutation is the same problem with a four-letter alphabet, and the balanced two-frontier idea is the conceptual gateway to A*.
Memory hook: Two waves; expand the smaller; meet in the middle.
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
"""LC 127. Word Ladder.
Bidirectional BFS over an implicit graph: words are nodes, edges are
one-letter edits. Always expand the smaller frontier; the moment a
generated candidate appears in the opposite frontier the two waves
have met and the answer is dist + 1. Branching factor b, depth d:
plain BFS touches ~b^d nodes, bidirectional ~2*b^(d/2).
"""
words = set(word_list)
if end_word not in words:
return 0
words.discard(begin_word)
front, back = {begin_word}, {end_word}
dist = 1
while front and back:
if len(front) > len(back):
front, back = back, front
next_front: set[str] = set()
for word in front:
for i in range(len(word)):
for ch in "abcdefghijklmnopqrstuvwxyz":
candidate = word[:i] + ch + word[i + 1:]
if candidate in back:
return dist + 1
if candidate in words:
words.discard(candidate) # visited = removed from pool
next_front.add(candidate)
front = next_front
dist += 1
return 0
// LC 127. Bidirectional BFS: always expand the smaller frontier; meeting
// the opposite frontier ends the search at dist + 1.
int ladderLength(string beginWord, string endWord, vector<string> wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
words.erase(beginWord);
unordered_set<string> front{beginWord}, back{endWord};
int dist = 1;
while (!front.empty() && !back.empty()) {
if (front.size() > back.size()) swap(front, back);
unordered_set<string> nextFront;
for (const string& word : front) {
string candidate = word;
for (size_t i = 0; i < candidate.size(); ++i) {
char original = candidate[i];
for (char ch = 'a'; ch <= 'z'; ++ch) {
candidate[i] = ch;
if (back.count(candidate)) return dist + 1;
if (words.count(candidate)) {
words.erase(candidate); // visited = removed from pool
nextFront.insert(candidate);
}
}
candidate[i] = original;
}
}
front = move(nextFront);
++dist;
}
return 0;
}
/// LC 127. Bidirectional BFS: always expand the smaller frontier; meeting
/// the opposite frontier ends the search at dist + 1.
pub fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
let mut words: HashSet<Vec<u8>> = word_list.into_iter().map(String::into_bytes).collect();
let end = end_word.into_bytes();
if !words.contains(&end) {
return 0;
}
let begin = begin_word.into_bytes();
words.remove(&begin);
let mut front = HashSet::from([begin]);
let mut back = HashSet::from([end]);
let mut dist = 1;
while !front.is_empty() && !back.is_empty() {
if front.len() > back.len() {
std::mem::swap(&mut front, &mut back);
}
let mut next_front = HashSet::new();
for word in &front {
let mut candidate = word.clone();
for i in 0..candidate.len() {
let original = candidate[i];
for ch in b'a'..=b'z' {
candidate[i] = ch;
if back.contains(&candidate) {
return dist + 1;
}
if words.remove(&candidate) {
// visited = removed from the pool
next_front.insert(candidate.clone());
}
}
candidate[i] = original;
}
}
front = next_front;
dist += 1;
}
0
}
/**
* LC 127. Bidirectional BFS: always expand the smaller frontier; meeting
* the opposite frontier ends the search at dist + 1.
*/
export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
words.delete(beginWord);
let front = new Set([beginWord]);
let back = new Set([endWord]);
let dist = 1;
const alphabet = "abcdefghijklmnopqrstuvwxyz";
while (front.size > 0 && back.size > 0) {
if (front.size > back.size) [front, back] = [back, front];
const nextFront = new Set<string>();
for (const word of front) {
for (let i = 0; i < word.length; i++) {
for (const ch of alphabet) {
const candidate = word.slice(0, i) + ch + word.slice(i + 1);
if (back.has(candidate)) return dist + 1;
if (words.has(candidate)) {
words.delete(candidate); // visited = removed from the pool
nextFront.add(candidate);
}
}
}
}
front = nextFront;
dist++;
}
return 0;
}
// LC 127. Bidirectional BFS: always expand the smaller frontier; meeting
// the opposite frontier ends the search at dist + 1.
func ladderLength(beginWord, endWord string, wordList []string) int {
words := make(map[string]bool, len(wordList))
for _, w := range wordList {
words[w] = true
}
if !words[endWord] {
return 0
}
delete(words, beginWord)
front := map[string]bool{beginWord: true}
back := map[string]bool{endWord: true}
dist := 1
for len(front) > 0 && len(back) > 0 {
if len(front) > len(back) {
front, back = back, front
}
nextFront := map[string]bool{}
for word := range front {
candidate := []byte(word)
for i := 0; i < len(candidate); i++ {
original := candidate[i]
for ch := byte('a'); ch <= 'z'; ch++ {
candidate[i] = ch
s := string(candidate)
if back[s] {
return dist + 1
}
if words[s] {
delete(words, s) // visited = removed from pool
nextFront[s] = true
}
}
candidate[i] = original
}
}
front = nextFront
dist++
}
return 0
}
// LC 127. Bidirectional BFS: expand the smaller frontier; meeting the opposite frontier ends at dist + 1.
func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
var words = Set(wordList)
if !words.contains(endWord) { return 0 }
words.remove(beginWord)
var front: Set<String> = [beginWord]
var back: Set<String> = [endWord]
var dist = 1
while !front.isEmpty && !back.isEmpty {
if front.count > back.count { swap(&front, &back) }
var nextFront: Set<String> = []
for word in front {
var candidate = Array(word)
for i in 0..<candidate.count {
let original = candidate[i]
for ch in "abcdefghijklmnopqrstuvwxyz" {
candidate[i] = ch
let neighbor = String(candidate)
if back.contains(neighbor) { return dist + 1 }
if words.contains(neighbor) {
words.remove(neighbor) // visited = removed from pool
nextFront.insert(neighbor)
}
}
candidate[i] = original
}
}
front = nextFront
dist += 1
}
return 0
}
5. Topological sort, Kahn's algorithm
LC 210 · Course Schedule II
Kahn's algorithm is BFS where readiness replaces adjacency: a node may enter the queue only when its indegree drops to zero, meaning every prerequisite is already placed in the output. Cycle detection falls out for free, because a node on a cycle waits on a predecessor that waits on it and never reaches indegree zero. If the finished order holds fewer than n nodes, the leftovers sit on a cycle and no valid order exists. O(V + E) time and space.
Memory hook: Indegree zero = ready to take.
def find_order_kahn(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
"""LC 210. Course Schedule II via Kahn's algorithm.
BFS where "ready" replaces "adjacent": a node enters the queue only
when its indegree hits zero, i.e. every prerequisite is already
placed. If the output is shorter than num_courses, the leftover nodes
sit on a cycle and no valid order exists. O(V + E) time and space.
"""
graph: list[list[int]] = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = deque(node for node in range(num_courses) if indegree[node] == 0)
order: list[int] = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else []
// LC 210 via Kahn: a node enters the queue when its indegree hits zero.
vector<int> findOrderKahn(int numCourses, vector<vector<int>> prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (const auto& p : prerequisites) {
graph[p[1]].push_back(p[0]);
++indegree[p[0]];
}
queue<int> q;
for (int node = 0; node < numCourses; ++node)
if (indegree[node] == 0) q.push(node);
vector<int> order;
while (!q.empty()) {
int node = q.front();
q.pop();
order.push_back(node);
for (int next : graph[node])
if (--indegree[next] == 0) q.push(next);
}
if (static_cast<int>(order.size()) != numCourses) order.clear();
return order;
}
/// LC 210 via Kahn: a node enters the queue when its indegree hits zero.
pub fn find_order_kahn(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
let n = num_courses as usize;
let mut graph = vec![Vec::new(); n];
let mut indegree = vec![0usize; n];
for p in &prerequisites {
graph[p[1] as usize].push(p[0] as usize);
indegree[p[0] as usize] += 1;
}
let mut queue: VecDeque<usize> = (0..n).filter(|&node| indegree[node] == 0).collect();
let mut order = Vec::with_capacity(n);
while let Some(node) = queue.pop_front() {
order.push(node as i32);
for &next in &graph[node] {
indegree[next] -= 1;
if indegree[next] == 0 {
queue.push_back(next);
}
}
}
if order.len() == n { order } else { Vec::new() }
}
/** LC 210 via Kahn: a node enters the queue when its indegree hits zero. */
export function findOrderKahn(numCourses: number, prerequisites: number[][]): number[] {
const graph: number[][] = Array.from({ length: numCourses }, () => []);
const indegree = new Array<number>(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
graph[prereq].push(course);
indegree[course]++;
}
const order: number[] = [];
for (let node = 0; node < numCourses; node++) {
if (indegree[node] === 0) order.push(node);
}
let head = 0; // the output array doubles as the queue
while (head < order.length) {
const node = order[head++];
for (const next of graph[node]) {
if (--indegree[next] === 0) order.push(next);
}
}
return order.length === numCourses ? order : [];
}
// LC 210 via Kahn: a node enters the queue when its indegree hits zero.
func findOrderKahn(numCourses int, prerequisites [][]int) []int {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, p := range prerequisites {
graph[p[1]] = append(graph[p[1]], p[0])
indegree[p[0]]++
}
queue := []int{}
for node := 0; node < numCourses; node++ {
if indegree[node] == 0 {
queue = append(queue, node)
}
}
order := []int{}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
order = append(order, node)
for _, next := range graph[node] {
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
if len(order) != numCourses {
return []int{}
}
return order
}
// LC 210 via Kahn: a node enters the queue when its indegree hits zero.
func findOrderKahn(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var graph = Array(repeating: [Int](), count: numCourses)
var indegree = Array(repeating: 0, count: numCourses)
for p in prerequisites {
graph[p[1]].append(p[0])
indegree[p[0]] += 1
}
var queue: [Int] = []
var head = 0
for node in 0..<numCourses where indegree[node] == 0 {
queue.append(node)
}
var order: [Int] = []
while head < queue.count {
let node = queue[head]
head += 1
order.append(node)
for next in graph[node] {
indegree[next] -= 1
if indegree[next] == 0 { queue.append(next) }
}
}
return order.count == numCourses ? order : []
}
6. 0-1 BFS
LC 2290 · Minimum Obstacle Removal to Reach Corner
Plain BFS needs equal edge weights and Dijkstra pays a logarithm per heap operation. When every edge costs exactly zero or one there is a middle path: relax edges like Dijkstra but use a deque, pushing free moves to the front and paid moves to the back. The deque stays sorted by distance with at most two distinct values in it, the same invariant that makes plain BFS correct, and every operation is O(1), giving O(mn) overall instead of O(mn log mn).
The same shape solves any problem that lets you flip a limited number of cells or walls, and it fixes the family relationship in your head: BFS, 0-1 BFS, and Dijkstra are one algorithm ordered by how general the weights are.
Memory hook: Free moves jump the line.
def min_obstacle_removal(grid: list[list[int]]) -> int:
"""LC 2290. Minimum Obstacle Removal to Reach Corner.
0-1 BFS: edge weight is 0 (empty cell) or 1 (remove an obstacle).
Use a deque instead of Dijkstra's heap -- weight-0 moves go to the
FRONT, weight-1 moves to the BACK, so the deque stays sorted by
distance and pops are O(1) instead of O(log n). O(mn) time and space.
"""
rows, cols = len(grid), len(grid[0])
inf = float("inf")
dist: list[list[float]] = [[inf] * cols for _ in range(rows)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols:
nd = dist[r][c] + grid[nr][nc]
if nd < dist[nr][nc]:
dist[nr][nc] = nd
if grid[nr][nc] == 0:
dq.appendleft((nr, nc))
else:
dq.append((nr, nc))
return int(dist[rows - 1][cols - 1])
// LC 2290. 0-1 BFS: deque, weight-0 edges to the front, weight-1 to the back.
int minObstacleRemoval(vector<vector<int>> grid) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
const int INF = 1 << 29;
vector<vector<int>> dist(rows, vector<int>(cols, INF));
dist[0][0] = 0;
deque<pair<int, int>> dq{{0, 0}};
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!dq.empty()) {
auto [r, c] = dq.front();
dq.pop_front();
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
int nd = dist[r][c] + grid[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
if (grid[nr][nc] == 0) dq.push_front({nr, nc});
else dq.push_back({nr, nc});
}
}
}
}
return dist[rows - 1][cols - 1];
}
/// LC 2290. 0-1 BFS: deque, weight-0 edges to the front, weight-1 to the back.
pub fn min_obstacle_removal(grid: Vec<Vec<i32>>) -> i32 {
let (rows, cols) = (grid.len(), grid[0].len());
let mut dist = vec![vec![i32::MAX; cols]; rows];
dist[0][0] = 0;
let mut dq = VecDeque::new();
dq.push_back((0usize, 0usize));
while let Some((r, c)) = dq.pop_front() {
let d = dist[r][c];
for (nr, nc) in [(r.wrapping_sub(1), c), (r + 1, c), (r, c.wrapping_sub(1)), (r, c + 1)] {
if nr < rows && nc < cols {
let nd = d + grid[nr][nc];
if nd < dist[nr][nc] {
dist[nr][nc] = nd;
if grid[nr][nc] == 0 {
dq.push_front((nr, nc));
} else {
dq.push_back((nr, nc));
}
}
}
}
}
dist[rows - 1][cols - 1]
}
const FOUR_DIRECTIONS: ReadonlyArray<readonly [number, number]> = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
/** LC 2290. 0-1 BFS: deque, weight-0 edges to the front, weight-1 to the back. */
export function minObstacleRemoval(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
const dist: number[][] = Array.from({ length: rows }, () => new Array<number>(cols).fill(Infinity));
dist[0][0] = 0;
const dq: [number, number][] = [[0, 0]];
while (dq.length > 0) {
const [r, c] = dq.shift()!; // fine for interview sizes; see module note
for (const [dr, dc] of FOUR_DIRECTIONS) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
const nd = dist[r][c] + grid[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
if (grid[nr][nc] === 0) dq.unshift([nr, nc]);
else dq.push([nr, nc]);
}
}
}
}
return dist[rows - 1][cols - 1];
}
// LC 2290. 0-1 BFS: deque, weight-0 edges to the front, weight-1 to the back.
func minObstacleRemoval(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
const inf = 1 << 29
dist := make([][]int, rows)
for r := range dist {
dist[r] = make([]int, cols)
for c := range dist[r] {
dist[r][c] = inf
}
}
dist[0][0] = 0
// Slice-based deque: head indexes the front, append grows the back, and a
// front-push reuses the slot just popped (prepends only when none is free).
dq := [][2]int{{0, 0}}
head := 0
dr := [4]int{1, -1, 0, 0}
dc := [4]int{0, 0, 1, -1}
for head < len(dq) {
r, c := dq[head][0], dq[head][1]
head++
for d := 0; d < 4; d++ {
nr, nc := r+dr[d], c+dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
nd := dist[r][c] + grid[nr][nc]
if nd < dist[nr][nc] {
dist[nr][nc] = nd
if grid[nr][nc] == 0 {
if head > 0 {
head--
dq[head] = [2]int{nr, nc}
} else {
dq = append([][2]int{{nr, nc}}, dq...)
}
} else {
dq = append(dq, [2]int{nr, nc})
}
}
}
}
}
return dist[rows-1][cols-1]
}
// LC 2290. 0-1 BFS: deque, weight-0 edges to the front, weight-1 to the back.
func minObstacleRemoval(_ grid: [[Int]]) -> Int {
let rows = grid.count, cols = grid[0].count
let inf = 1 << 29
var dist = Array(repeating: Array(repeating: inf, count: cols), count: rows)
dist[0][0] = 0
// two-array deque: front pushes/pops are LIFO on one array, back pushes go to a head-indexed queue
var frontStack: [(Int, Int)] = [(0, 0)]
var backQueue: [(Int, Int)] = []
var backHead = 0
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
while !frontStack.isEmpty || backHead < backQueue.count {
let cell: (Int, Int)
if let fromFront = frontStack.popLast() {
cell = fromFront
} else {
cell = backQueue[backHead]
backHead += 1
}
let (r, c) = cell
for d in 0..<4 {
let nr = r + dr[d], nc = c + dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
let nd = dist[r][c] + grid[nr][nc]
if nd < dist[nr][nc] {
dist[nr][nc] = nd
if grid[nr][nc] == 0 {
frontStack.append((nr, nc))
} else {
backQueue.append((nr, nc))
}
}
}
}
}
return dist[rows - 1][cols - 1]
}
7. Flood fill and connected components
LC 200 · Number of Islands · recursive
The outer double loop scans every cell, and on finding land it increments the count and launches a DFS that sinks the entire island by overwriting every reachable cell. Because the whole component is erased before the scan continues, no island can be counted twice, so the number of components equals the number of launches. Mutating the grid doubles as the visited set, which costs no extra memory; copy first if the caller needs the grid back. O(mn) time, with recursion as deep as the largest island in the worst case.
Memory hook: Count the launches, sink the island.
def num_islands(grid: list[list[str]]) -> int:
"""LC 200. Number of Islands (recursive flood fill).
Outer loop scans every cell; each DFS sinks one whole island by
overwriting '1' with '0', so the outer loop can never count the same
island twice. Components found = DFS launches. O(mn) time,
O(mn) recursion stack in the worst case (all land).
"""
rows, cols = len(grid), len(grid[0])
def sink(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0"
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
sink(r, c)
return count
// LC 200, recursive flood fill: each DFS launch sinks one whole island.
static void sink(vector<vector<char>>& grid, int r, int c) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
grid[r][c] = '0';
sink(grid, r + 1, c);
sink(grid, r - 1, c);
sink(grid, r, c + 1);
sink(grid, r, c - 1);
}
int numIslands(vector<vector<char>> grid) {
int count = 0;
for (int r = 0; r < static_cast<int>(grid.size()); ++r)
for (int c = 0; c < static_cast<int>(grid[0].size()); ++c)
if (grid[r][c] == '1') {
++count;
sink(grid, r, c);
}
return count;
}
/// LC 200, recursive flood fill: each DFS launch sinks one whole island.
pub fn num_islands(mut grid: Vec<Vec<char>>) -> i32 {
fn sink(grid: &mut Vec<Vec<char>>, r: usize, c: usize) {
if r >= grid.len() || c >= grid[0].len() || grid[r][c] != '1' {
return;
}
grid[r][c] = '0';
sink(grid, r + 1, c);
sink(grid, r.wrapping_sub(1), c);
sink(grid, r, c + 1);
sink(grid, r, c.wrapping_sub(1));
}
let mut count = 0;
for r in 0..grid.len() {
for c in 0..grid[0].len() {
if grid[r][c] == '1' {
count += 1;
sink(&mut grid, r, c);
}
}
}
count
}
/** LC 200, recursive flood fill: each DFS launch sinks one whole island. */
export function numIslands(grid: string[][]): number {
const rows = grid.length;
const cols = grid[0].length;
function sink(r: number, c: number): void {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") return;
grid[r][c] = "0";
sink(r + 1, c);
sink(r - 1, c);
sink(r, c + 1);
sink(r, c - 1);
}
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === "1") {
count++;
sink(r, c);
}
}
}
return count;
}
// LC 200, recursive flood fill: each DFS launch sinks one whole island.
func numIslands(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
var sink func(r, c int)
sink = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
return
}
grid[r][c] = '0'
sink(r+1, c)
sink(r-1, c)
sink(r, c+1)
sink(r, c-1)
}
count := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
sink(r, c)
}
}
}
return count
}
// LC 200, recursive flood fill: each DFS launch sinks one whole island.
func numIslands(_ grid: [[Character]]) -> Int {
var grid = grid
let rows = grid.count, cols = grid[0].count
func sink(_ r: Int, _ c: Int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != "1" { return }
grid[r][c] = "0"
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
}
var count = 0
for r in 0..<rows {
for c in 0..<cols where grid[r][c] == "1" {
count += 1
sink(r, c)
}
}
return count
}
8. Iterative DFS with an explicit stack
LC 200 again · the recursion-free fallback
Recursion depth equals the worst path length, and a snake-shaped island in a thousand-by-thousand grid overflows the default call stack in most languages. The fix is the same logic with the call stack swapped for an explicit one: push the seed, then loop popping and pushing unmarked neighbors, marking each on push rather than on pop. Marking on pop reintroduces the duplicate-entry problem from the BFS section, in stack form.
Put side by side with BFS, the only difference is the container. A stack dives, a queue spreads, and if a problem needs only reachability either works, while distances demand the queue.
Memory hook: Stack or queue is the only difference.
def num_islands_iterative(grid: list[list[str]]) -> int:
"""LC 200 with an explicit stack -- the recursion-free fallback.
Identical logic; swap the call stack for a list. Pop order differs
from the recursive version but flood fill only needs reachability,
not ordering, so the answer is unchanged. Use this shape whenever
the grid may be deep enough to overflow recursion limits.
"""
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
count += 1
stack = [(r, c)]
grid[r][c] = "0"
while stack:
cr, cc = stack.pop()
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0" # mark on push, not on pop
stack.append((nr, nc))
return count
// LC 200 with an explicit stack -- the recursion-free fallback.
int numIslandsIterative(vector<vector<char>> grid) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int count = 0;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) {
if (grid[r][c] != '1') continue;
++count;
vector<pair<int, int>> stack{{r, c}};
grid[r][c] = '0';
while (!stack.empty()) {
auto [cr, cc] = stack.back();
stack.pop_back();
for (int d = 0; d < 4; ++d) {
int nr = cr + dr[d], nc = cc + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
grid[nr][nc] = '0'; // mark on push, not on pop
stack.push_back({nr, nc});
}
}
}
}
return count;
}
/// LC 200 with an explicit stack -- the recursion-free fallback.
pub fn num_islands_iterative(mut grid: Vec<Vec<char>>) -> i32 {
let (rows, cols) = (grid.len(), grid[0].len());
let mut count = 0;
for r in 0..rows {
for c in 0..cols {
if grid[r][c] != '1' {
continue;
}
count += 1;
let mut stack = vec![(r, c)];
grid[r][c] = '0';
while let Some((cr, cc)) = stack.pop() {
for (nr, nc) in [(cr.wrapping_sub(1), cc), (cr + 1, cc), (cr, cc.wrapping_sub(1)), (cr, cc + 1)] {
if nr < rows && nc < cols && grid[nr][nc] == '1' {
grid[nr][nc] = '0'; // mark on push, not on pop
stack.push((nr, nc));
}
}
}
}
}
count
}
const FOUR_DIRECTIONS: ReadonlyArray<readonly [number, number]> = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
/** LC 200 with an explicit stack -- the recursion-free fallback. */
export function numIslandsIterative(grid: string[][]): number {
const rows = grid.length;
const cols = grid[0].length;
let count = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== "1") continue;
count++;
const stack: [number, number][] = [[r, c]];
grid[r][c] = "0";
while (stack.length > 0) {
const [cr, cc] = stack.pop()!;
for (const [dr, dc] of FOUR_DIRECTIONS) {
const nr = cr + dr;
const nc = cc + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === "1") {
grid[nr][nc] = "0"; // mark on push, not on pop
stack.push([nr, nc]);
}
}
}
}
}
return count;
}
// LC 200 with an explicit stack -- the recursion-free fallback.
func numIslandsIterative(grid [][]byte) int {
rows, cols := len(grid), len(grid[0])
dr := [4]int{1, -1, 0, 0}
dc := [4]int{0, 0, 1, -1}
count := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] != '1' {
continue
}
count++
stack := [][2]int{{r, c}}
grid[r][c] = '0'
for len(stack) > 0 {
cr, cc := stack[len(stack)-1][0], stack[len(stack)-1][1]
stack = stack[:len(stack)-1]
for d := 0; d < 4; d++ {
nr, nc := cr+dr[d], cc+dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1' {
grid[nr][nc] = '0' // mark on push, not on pop
stack = append(stack, [2]int{nr, nc})
}
}
}
}
}
return count
}
// LC 200 with an explicit stack -- the recursion-free fallback.
func numIslandsIterative(_ grid: [[Character]]) -> Int {
var grid = grid
let rows = grid.count, cols = grid[0].count
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
var count = 0
for r in 0..<rows {
for c in 0..<cols {
if grid[r][c] != "1" { continue }
count += 1
var stack: [(Int, Int)] = [(r, c)]
grid[r][c] = "0"
while let (cr, cc) = stack.popLast() {
for d in 0..<4 {
let nr = cr + dr[d], nc = cc + dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == "1" {
grid[nr][nc] = "0" // mark on push, not on pop
stack.append((nr, nc))
}
}
}
}
}
return count
}
9. Cycle detection with three colors
LC 207 · Course Schedule
In a directed graph, reaching an already-visited node is ambiguous. Reaching it through a back edge, meaning it sits on the current recursion path, proves a cycle; reaching it through a cross edge, meaning an earlier search finished it, is harmless. A boolean visited flag cannot tell these apart, and the diamond graph with edges 0 to 1, 0 to 2, and 1 to 2 is the standard case where the boolean version reports a cycle that does not exist.
Three states make the distinction: white for untouched, gray for open on the current path, black for fully explored and proven safe. Meeting gray means a cycle; meeting black means skip. O(V + E) time and O(V) space.
Memory hook: Gray means still inside it; meeting gray means a loop.
WHITE, GRAY, BLACK = 0, 1, 2 # unvisited / on current path / fully explored
def can_finish_dfs(num_courses: int, prerequisites: list[list[int]]) -> bool:
"""LC 207. Course Schedule via 3-color cycle detection.
GRAY means "on the current recursion path". Meeting a GRAY node is a
back edge -- a cycle. Meeting a BLACK node is fine: it was fully
explored by an earlier call and proved cycle-free. A plain boolean
visited set cannot tell these two cases apart; that is the classic
wrong answer on this problem. O(V + E) time and space.
"""
graph: list[list[int]] = [[] for _ in range(num_courses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
color = [WHITE] * num_courses
def has_cycle(node: int) -> bool:
color[node] = GRAY
for nxt in graph[node]:
if color[nxt] == GRAY:
return True
if color[nxt] == WHITE and has_cycle(nxt):
return True
color[node] = BLACK
return False
for node in range(num_courses):
if color[node] == WHITE and has_cycle(node):
return False
return True
// 3-color states: 0 = unvisited, 1 = on current path, 2 = fully explored.
enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };
static bool hasCycle(const vector<vector<int>>& graph, vector<int>& color, int node) {
color[node] = GRAY;
for (int next : graph[node]) {
if (color[next] == GRAY) return true; // back edge = cycle
if (color[next] == WHITE && hasCycle(graph, color, next)) return true;
}
color[node] = BLACK;
return false;
}
// LC 207. GRAY hit = cycle; BLACK hit = already proven safe.
bool canFinishDFS(int numCourses, vector<vector<int>> prerequisites) {
vector<vector<int>> graph(numCourses);
for (const auto& p : prerequisites) graph[p[1]].push_back(p[0]);
vector<int> color(numCourses, WHITE);
for (int node = 0; node < numCourses; ++node)
if (color[node] == WHITE && hasCycle(graph, color, node)) return false;
return true;
}
// 3-color states: unvisited / on current path / fully explored.
const WHITE: u8 = 0;
const GRAY: u8 = 1;
const BLACK: u8 = 2;
/// LC 207. GRAY hit = back edge = cycle; BLACK hit = already proven safe.
pub fn can_finish_dfs(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let n = num_courses as usize;
let mut graph = vec![Vec::new(); n];
for p in &prerequisites {
graph[p[1] as usize].push(p[0] as usize);
}
fn has_cycle(graph: &[Vec<usize>], color: &mut [u8], node: usize) -> bool {
color[node] = GRAY;
for &next in &graph[node] {
if color[next] == GRAY {
return true;
}
if color[next] == WHITE && has_cycle(graph, color, next) {
return true;
}
}
color[node] = BLACK;
false
}
let mut color = vec![WHITE; n];
(0..n).all(|node| color[node] != WHITE || !has_cycle(&graph, &mut color, node))
}
// 3-color states: unvisited / on current path / fully explored.
const WHITE = 0;
const GRAY = 1;
const BLACK = 2;
/** LC 207. GRAY hit = back edge = cycle; BLACK hit = already proven safe. */
export function canFinishDFS(numCourses: number, prerequisites: number[][]): boolean {
const graph: number[][] = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) graph[prereq].push(course);
const color = new Array<number>(numCourses).fill(WHITE);
function hasCycle(node: number): boolean {
color[node] = GRAY;
for (const next of graph[node]) {
if (color[next] === GRAY) return true;
if (color[next] === WHITE && hasCycle(next)) return true;
}
color[node] = BLACK;
return false;
}
for (let node = 0; node < numCourses; node++) {
if (color[node] === WHITE && hasCycle(node)) return false;
}
return true;
}
// LC 207. 3-color cycle detection: GRAY hit = cycle; BLACK hit = already proven safe.
func canFinishDFS(numCourses int, prerequisites [][]int) bool {
const (
white = 0 // unvisited
gray = 1 // on current recursion path
black = 2 // fully explored
)
graph := make([][]int, numCourses)
for _, p := range prerequisites {
graph[p[1]] = append(graph[p[1]], p[0])
}
color := make([]int, numCourses) // zero value = white
var hasCycle func(node int) bool
hasCycle = func(node int) bool {
color[node] = gray
for _, next := range graph[node] {
if color[next] == gray {
return true // back edge = cycle
}
if color[next] == white && hasCycle(next) {
return true
}
}
color[node] = black
return false
}
for node := 0; node < numCourses; node++ {
if color[node] == white && hasCycle(node) {
return false
}
}
return true
}
// LC 207. 3-color cycle detection: a GRAY hit is a back edge (cycle), a BLACK hit is already proven safe.
func canFinishDFS(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
let white = 0, gray = 1, black = 2 // unvisited / on current path / fully explored
var graph = Array(repeating: [Int](), count: numCourses)
for p in prerequisites { graph[p[1]].append(p[0]) }
var color = Array(repeating: white, count: numCourses)
func hasCycle(_ node: Int) -> Bool {
color[node] = gray
for next in graph[node] {
if color[next] == gray { return true } // back edge = cycle
if color[next] == white && hasCycle(next) { return true }
}
color[node] = black
return false
}
for node in 0..<numCourses where color[node] == white {
if hasCycle(node) { return false }
}
return true
}
10. Topological sort by finish times
LC 210 · Course Schedule II · the DFS twin of Kahn's
One line added to cycle detection produces a topological sort: append each node when it turns black, then reverse the list. A node is appended only after everything it points to has been appended, so the reversed finish order puts every node ahead of its dependents, which is the definition.
Knowing both algorithms is worth saying out loud in an interview. Kahn's yields the order lazily round by round, which answers questions like how many semesters, while the DFS version yields finish times, which later algorithms such as Kosaraju's strongly connected components are built on.
Memory hook: Finish last, serve first.
WHITE, GRAY, BLACK = 0, 1, 2 # unvisited / on current path / fully explored
def find_order_dfs(num_courses: int, prerequisites: list[list[int]]) -> list[int]:
"""LC 210. Course Schedule II via DFS finish times.
Postorder append: a node is appended only after every node it points
to is already in the list, so reversing the finish order makes all
edges point forward. Returns [] when a cycle is found. This is the
DFS twin of Kahn's algorithm. O(V + E) time and space.
"""
graph: list[list[int]] = [[] for _ in range(num_courses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
color = [WHITE] * num_courses
order: list[int] = []
def visit(node: int) -> bool:
color[node] = GRAY
for nxt in graph[node]:
if color[nxt] == GRAY:
return False
if color[nxt] == WHITE and not visit(nxt):
return False
color[node] = BLACK
order.append(node)
return True
for node in range(num_courses):
if color[node] == WHITE and not visit(node):
return []
order.reverse()
return order
// 3-color states: 0 = unvisited, 1 = on current path, 2 = fully explored.
enum Color { WHITE = 0, GRAY = 1, BLACK = 2 };
static bool topoVisit(const vector<vector<int>>& graph, vector<int>& color, vector<int>& order, int node) {
color[node] = GRAY;
for (int next : graph[node]) {
if (color[next] == GRAY) return false;
if (color[next] == WHITE && !topoVisit(graph, color, order, next)) return false;
}
color[node] = BLACK;
order.push_back(node); // postorder: appended after all dependents
return true;
}
// LC 210 via DFS finish times: reversed postorder is a topological order.
vector<int> findOrderDFS(int numCourses, vector<vector<int>> prerequisites) {
vector<vector<int>> graph(numCourses);
for (const auto& p : prerequisites) graph[p[1]].push_back(p[0]);
vector<int> color(numCourses, WHITE);
vector<int> order;
for (int node = 0; node < numCourses; ++node)
if (color[node] == WHITE && !topoVisit(graph, color, order, node))
return {};
reverse(order.begin(), order.end());
return order;
}
// 3-color states: unvisited / on current path / fully explored.
const WHITE: u8 = 0;
const GRAY: u8 = 1;
const BLACK: u8 = 2;
/// LC 210 via DFS finish times: reversed postorder is a topological order.
pub fn find_order_dfs(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> Vec<i32> {
let n = num_courses as usize;
let mut graph = vec![Vec::new(); n];
for p in &prerequisites {
graph[p[1] as usize].push(p[0] as usize);
}
fn visit(graph: &[Vec<usize>], color: &mut [u8], order: &mut Vec<i32>, node: usize) -> bool {
color[node] = GRAY;
for &next in &graph[node] {
if color[next] == GRAY {
return false;
}
if color[next] == WHITE && !visit(graph, color, order, next) {
return false;
}
}
color[node] = BLACK;
order.push(node as i32); // postorder: appended after all dependents
true
}
let mut color = vec![WHITE; n];
let mut order = Vec::with_capacity(n);
for node in 0..n {
if color[node] == WHITE && !visit(&graph, &mut color, &mut order, node) {
return Vec::new();
}
}
order.reverse();
order
}
// 3-color states: unvisited / on current path / fully explored.
const WHITE = 0;
const GRAY = 1;
const BLACK = 2;
/** LC 210 via DFS finish times: reversed postorder is a topological order. */
export function findOrderDFS(numCourses: number, prerequisites: number[][]): number[] {
const graph: number[][] = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) graph[prereq].push(course);
const color = new Array<number>(numCourses).fill(WHITE);
const order: number[] = [];
function visit(node: number): boolean {
color[node] = GRAY;
for (const next of graph[node]) {
if (color[next] === GRAY) return false;
if (color[next] === WHITE && !visit(next)) return false;
}
color[node] = BLACK;
order.push(node); // postorder: appended after all dependents
return true;
}
for (let node = 0; node < numCourses; node++) {
if (color[node] === WHITE && !visit(node)) return [];
}
return order.reverse();
}
// LC 210 via DFS finish times: reversed postorder is a topological order.
func findOrderDFS(numCourses int, prerequisites [][]int) []int {
const (
white = 0 // unvisited
gray = 1 // on current recursion path
black = 2 // fully explored
)
graph := make([][]int, numCourses)
for _, p := range prerequisites {
graph[p[1]] = append(graph[p[1]], p[0])
}
color := make([]int, numCourses) // zero value = white
order := []int{}
var visit func(node int) bool
visit = func(node int) bool {
color[node] = gray
for _, next := range graph[node] {
if color[next] == gray {
return false
}
if color[next] == white && !visit(next) {
return false
}
}
color[node] = black
order = append(order, node) // postorder: appended after all dependents
return true
}
for node := 0; node < numCourses; node++ {
if color[node] == white && !visit(node) {
return []int{}
}
}
for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 {
order[i], order[j] = order[j], order[i]
}
return order
}
// LC 210 via DFS finish times: reversed postorder is a topological order.
func findOrderDFS(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
let white = 0, gray = 1, black = 2 // unvisited / on current path / fully explored
var graph = Array(repeating: [Int](), count: numCourses)
for p in prerequisites { graph[p[1]].append(p[0]) }
var color = Array(repeating: white, count: numCourses)
var order: [Int] = []
func visit(_ node: Int) -> Bool {
color[node] = gray
for next in graph[node] {
if color[next] == gray { return false }
if color[next] == white && !visit(next) { return false }
}
color[node] = black
order.append(node) // postorder: appended after all dependents
return true
}
for node in 0..<numCourses where color[node] == white {
if !visit(node) { return [] }
}
return order.reversed()
}
11. Postorder tree DFS with return values
LC 543 · Diameter of Binary Tree
Each recursive call returns one fact about its subtree to its parent, the height, while a shared best collects a different fact computed from the children, the longest path bending through this node. The answer is the collected value, not the root's return value, and that mismatch is the whole trick. Computing heights independently at every node would be quadratic; the postorder version computes each height exactly once, O(n) time and O(height) stack.
Balanced Binary Tree, Binary Tree Maximum Path Sum, Longest Univalue Path, and House Robber III are this exact shape with a different combine step.
Memory hook: Return what the parent needs; stash what the answer needs.
def diameter_of_binary_tree(root: Optional[TreeNode]) -> int:
"""LC 543. Diameter of Binary Tree -- the postorder return-value pattern.
Each call returns one fact (height) while a nonlocal best collects a
different fact (longest path through this node = left height + right
height). Dozens of tree problems are this exact shape with a
different combine step. O(n) time, O(height) stack.
"""
best = 0
def height(node: Optional[TreeNode]) -> int:
nonlocal best
if not node:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best
// LC 543. Postorder return-value pattern: return height, collect diameter.
static int height(TreeNode* node, int& best) {
if (!node) return 0;
int left = height(node->left, best);
int right = height(node->right, best);
best = max(best, left + right);
return 1 + max(left, right);
}
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
height(root, best);
return best;
}
/// LC 543. Postorder return-value pattern: return height, collect diameter.
pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn height(node: &Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
match node {
None => 0,
Some(rc) => {
let n = rc.borrow();
let left = height(&n.left, best);
let right = height(&n.right, best);
*best = (*best).max(left + right);
1 + left.max(right)
}
}
}
let mut best = 0;
height(&root, &mut best);
best
}
/** LC 543. Postorder return-value pattern: return height, collect diameter. */
export function diameterOfBinaryTree(root: TreeNode | null): number {
let best = 0;
function height(node: TreeNode | null): number {
if (!node) return 0;
const left = height(node.left);
const right = height(node.right);
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
}
height(root);
return best;
}
// LC 543. Postorder return-value pattern: return height, collect diameter.
func diameterOfBinaryTree(root *TreeNode) int {
best := 0
var height func(node *TreeNode) int
height = func(node *TreeNode) int {
if node == nil {
return 0
}
left := height(node.Left)
right := height(node.Right)
if left+right > best {
best = left + right
}
if left > right {
return 1 + left
}
return 1 + right
}
height(root)
return best
}
// LC 543. Postorder return-value pattern: return height, collect diameter.
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
var best = 0
func height(_ node: TreeNode?) -> Int {
guard let node = node else { return 0 }
let left = height(node.left)
let right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
}
_ = height(root)
return best
}
12. Backtracking on a grid
LC 79 · Word Search · DFS plus undo
Flood fill marks cells permanently because visited is a global fact there. Here a cell is only blocked for the current path, and a different path may use it, so the mark is temporary: overwrite the cell, recurse on the four neighbors for the next character, then restore the cell before returning so sibling paths can reuse it. DFS plus undo is the definition of backtracking, and the test suites include a word that only fits by snaking through cells freed when earlier branches failed.
The check order matters too: test for a complete match before bounds, or the final character fails at the grid edge. Time is O(mn · 3^L), branching three ways because the path never returns to the cell it came from, with O(L) stack.
Memory hook: Mark, explore, unmark.
def exist(board: list[list[str]], word: str) -> bool:
"""LC 79. Word Search -- DFS plus undo, i.e. backtracking.
The mark is temporary: overwrite the cell with '#' so the current
path cannot reuse it, then RESTORE it before returning so sibling
paths can. Permanent marking is the classic wrong answer here.
O(mn * 3^L) time (3 because we never go back where we came from),
O(L) stack.
"""
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
return False
saved, board[r][c] = board[r][c], "#"
found = (
dfs(r + 1, c, i + 1)
or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1)
or dfs(r, c - 1, i + 1)
)
board[r][c] = saved
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
static bool wordDfs(vector<vector<char>>& board, const string& word, int r, int c, size_t i) {
if (i == word.size()) return true;
int rows = static_cast<int>(board.size()), cols = static_cast<int>(board[0].size());
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i]) return false;
char saved = board[r][c];
board[r][c] = '#';
bool found = wordDfs(board, word, r + 1, c, i + 1) || wordDfs(board, word, r - 1, c, i + 1) ||
wordDfs(board, word, r, c + 1, i + 1) || wordDfs(board, word, r, c - 1, i + 1);
board[r][c] = saved;
return found;
}
bool exist(vector<vector<char>> board, string word) {
for (int r = 0; r < static_cast<int>(board.size()); ++r)
for (int c = 0; c < static_cast<int>(board[0].size()); ++c)
if (wordDfs(board, word, r, c, 0)) return true;
return false;
}
/// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
let word: Vec<char> = word.chars().collect();
fn dfs(board: &mut Vec<Vec<char>>, word: &[char], r: usize, c: usize, i: usize) -> bool {
if i == word.len() {
return true;
}
if r >= board.len() || c >= board[0].len() || board[r][c] != word[i] {
return false;
}
let saved = board[r][c];
board[r][c] = '#';
let found = dfs(board, word, r + 1, c, i + 1)
|| dfs(board, word, r.wrapping_sub(1), c, i + 1)
|| dfs(board, word, r, c + 1, i + 1)
|| dfs(board, word, r, c.wrapping_sub(1), i + 1);
board[r][c] = saved;
found
}
for r in 0..board.len() {
for c in 0..board[0].len() {
if dfs(&mut board, &word, r, c, 0) {
return true;
}
}
}
false
}
/** LC 79. DFS + undo = backtracking: mark '#', recurse, restore. */
export function exist(board: string[][], word: string): boolean {
const rows = board.length;
const cols = board[0].length;
function dfs(r: number, c: number, i: number): boolean {
if (i === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
const saved = board[r][c];
board[r][c] = "#";
const found =
dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
board[r][c] = saved;
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
func exist(board [][]byte, word string) bool {
rows, cols := len(board), len(board[0])
var dfs func(r, c, i int) bool
dfs = func(r, c, i int) bool {
if i == len(word) {
return true
}
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i] {
return false
}
saved := board[r][c]
board[r][c] = '#'
found := dfs(r+1, c, i+1) || dfs(r-1, c, i+1) ||
dfs(r, c+1, i+1) || dfs(r, c-1, i+1)
board[r][c] = saved
return found
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
// LC 79. DFS + undo = backtracking: mark '#', recurse, restore.
func exist(_ board: [[Character]], _ word: String) -> Bool {
var board = board
let rows = board.count, cols = board[0].count
let target = Array(word)
func dfs(_ r: Int, _ c: Int, _ i: Int) -> Bool {
if i == target.count { return true }
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != target[i] { return false }
let saved = board[r][c]
board[r][c] = "#"
let found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1)
|| dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1)
board[r][c] = saved
return found
}
for r in 0..<rows {
for c in 0..<cols {
if dfs(r, c, 0) { return true }
}
}
return false
}
Where the code lives
The implementations and their test suites live in a local interview-prep repository,
with the Python versions under python/graph_traversal/, C++ as a
self-contained assert suite, Rust as a library module with inline tests, TypeScript
checked by both ts-node assertions and the compiler, Go as a package with go test
suites, and Swift compiled and asserted against the same cases. The longer written
treatment of each variant, including the naive baselines and follow-up questions, is in the
BFS and
DFS notes.