Jun 21, 2025

Breadth-First Search

Overview

Breadth-first search explores every state at distance d before any state at distance d + 1. A queue preserves this order, so the first time BFS reaches a state is through a shortest path in an unweighted graph. Capture the queue size before processing a level when the algorithm needs the current depth, number of moves, or all values on that level.

On a binary tree, the left and right references define the neighbors. A normal downward traversal has no cycles, so it does not need a visited set. Tree problems often process one complete level at a time or attach extra information such as a node’s row, column, or conceptual position. If parent links are added, the tree becomes an undirected graph and needs a visited set.

On an adjacency-list graph, shared paths and cycles are possible. Mark a node visited when it is enqueued, not when it is removed, so it enters the queue only once. Some problems build the adjacency structure indirectly: wildcard patterns connect words, stops connect bus routes, and generated moves connect coordinate states. Once the graph exists, BFS takes O(V + E) time and O(V) space.

A matrix is an implicit graph whose cells are nodes and whose neighbors are usually the four adjacent coordinates. Check bounds and the cell condition before enqueueing a neighbor, then mark it immediately. Multi-source BFS starts with every source in the queue and expands them together, producing the distance to the nearest source in O(R * C) time.

Templates

Binary tree

Return immediately if root is null.
Enqueue the root, then capture N = dq.size() before each level.
Remove exactly N nodes, process their values, and enqueue their non-null children.
A visited set is unnecessary unless traversal can move back to a parent.

import java.util.*;

public class TreeBfsTemplate {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<>();
		if (root == null) {
			return res;
		}

		Deque<TreeNode> dq = new ArrayDeque<>();
		dq.addLast(root);

		while (!dq.isEmpty()) {
			int N = dq.size();
			List<Integer> level = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				TreeNode node = dq.removeFirst();
				level.add(node.val);
				if (node.left != null) {
					dq.addLast(node.left);
				}
				if (node.right != null) {
					dq.addLast(node.right);
				}
			}
			res.add(level);
		}

		return res;
	}
}

from collections import deque

def level_order(root) -> list[list[int]]:
    if not root:
        return []

    res = []
    dq = deque([root])

    while dq:
        level = []
        for _ in range(len(dq)):
            node = dq.popleft()
            level.append(node.val)
            if node.left:
                dq.append(node.left)
            if node.right:
                dq.append(node.right)
        res.append(level)

    return res

Adjacency-list graph

Enqueue start and add it to seen immediately.
Process the queue one level at a time when an edge count or shortest distance is needed.
For each node, enqueue every unseen neighbor from its adjacency list.
Return as soon as the target is removed from the queue.

import java.util.*;

public class GraphBfsTemplate {
	public int shortestDistance(List<List<Integer>> graph, int start, int target) {
		Deque<Integer> dq = new ArrayDeque<>();
		dq.addLast(start);
		Set<Integer> seen = new HashSet<>();
		seen.add(start);
		int distance = 0;

		while (!dq.isEmpty()) {
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				int node = dq.removeFirst();
				if (node == target) {
					return distance;
				}

				for (int nei : graph.get(node)) {
					if (!seen.contains(nei)) {
						seen.add(nei);
						dq.addLast(nei);
					}
				}
			}
			distance++;
		}

		return -1;
	}
}

from collections import deque

def shortest_distance(graph: list[list[int]], start: int, target: int) -> int:
    dq = deque([start])
    seen = {start}
    distance = 0

    while dq:
        for _ in range(len(dq)):
            node = dq.popleft()
            if node == target:
                return distance

            for nei in graph[node]:
                if nei not in seen:
                    seen.add(nei)
                    dq.append(nei)
        distance += 1

    return -1

Matrix

Enqueue every source cell and assign it distance 0.
Remove one coordinate and examine its four adjacent coordinates.
Skip out-of-bounds and already visited cells.
Assign a valid neighbor the current distance plus one before enqueueing it.

import java.util.*;

public class MatrixBfsTemplate {
	public int[][] distanceFromNearestZero(int[][] matrix) {
		int R = matrix.length;
		int C = matrix[0].length;
		int[][] distance = new int[R][C];
		Deque<int[]> dq = new ArrayDeque<>();

		for (int r = 0; r < R; r++) {
			Arrays.fill(distance[r], -1);
			for (int c = 0; c < C; c++) {
				if (matrix[r][c] == 0) {
					distance[r][c] = 0;
					dq.addLast(new int[] {r, c});
				}
			}
		}

		int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		while (!dq.isEmpty()) {
			int[] curr = dq.removeFirst();
			int currR = curr[0];
			int currC = curr[1];

			for (int[] dir : dirs) {
				int nextR = currR + dir[0];
				int nextC = currC + dir[1];
				if (nextR >= 0 && nextR < R &&
					nextC >= 0 && nextC < C &&
					distance[nextR][nextC] == -1) {
					distance[nextR][nextC] = distance[currR][currC] + 1;
					dq.addLast(new int[] {nextR, nextC});
				}
			}
		}

		return distance;
	}
}

from collections import deque

def distance_from_nearest_zero(matrix: list[list[int]]) -> list[list[int]]:
    R, C = len(matrix), len(matrix[0])
    distance = [[-1] * C for _ in range(R)]
    dq = deque()

    for r in range(R):
        for c in range(C):
            if matrix[r][c] == 0:
                distance[r][c] = 0
                dq.append((r, c))

    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while dq:
        curr_r, curr_c = dq.popleft()
        for dr, dc in dirs:
            next_r = curr_r + dr
            next_c = curr_c + dc
            if 0 <= next_r < R and 0 <= next_c < C and distance[next_r][next_c] == -1:
                distance[next_r][next_c] = distance[curr_r][curr_c] + 1
                dq.append((next_r, next_c))

    return distance

Problems

199. Binary Tree Right Side View

Process the tree one level at a time. Since left children are enqueued before right children, the last node removed from the deque at each level is the node visible from the right side.

import java.util.*;

class Solution {
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}

		Deque<TreeNode> dq = new ArrayDeque<>();
		dq.addLast(root);

		while (!dq.isEmpty()) {
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				TreeNode node = dq.removeFirst();
				if (i == N - 1) {
					res.add(node.val);
				}
				if (node.left != null) {
					dq.addLast(node.left);
				}
				if (node.right != null) {
					dq.addLast(node.right);
				}
			}
		}

		return res;
	}
}

import collections
from typing import List, Optional

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res

        dq = collections.deque([root])

        while dq:
            N = len(dq)
            for i in range(N):
                node = dq.popleft()
                if i == N-1:
                    res.append(node.val)
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)

        return res

103. Binary Tree Zigzag Level Order Traversal

Collect each tree level with a standard left-to-right BFS. Reverse every other completed level before appending it to res, then toggle flip for the next level.

import java.util.*;

class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> res = new ArrayList<>();
		if (root == null) {
			return res;
		}

		Deque<TreeNode> dq = new ArrayDeque<>();
		dq.addLast(root);
		boolean flip = false;

		while (!dq.isEmpty()) {
			List<Integer> level = new ArrayList<>();
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				TreeNode node = dq.removeFirst();
				level.add(node.val);
				if (node.left != null) {
					dq.addLast(node.left);
				}
				if (node.right != null) {
					dq.addLast(node.right);
				}
			}

			if (flip) {
				Collections.reverse(level);
			}
			flip = !flip;
			res.add(level);
		}

		return res;
	}
}

import collections
from typing import List, Optional

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        dq = collections.deque()
        dq.append(root)
        flip = False

        while dq:
            level = []
            for _ in range(len(dq)):
                node = dq.popleft()
                level.append(node.val)
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
            if flip:
                level = level[::-1]
            flip = not flip
            res.append(level)

        return res

662. Maximum Width of Binary Tree

Assign each node its position in a conceptual complete binary tree: a node at w gives its children positions 2 * w and 2 * w + 1. At each level, the distance between the first and last positions gives its width, including null positions between real nodes.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int widthOfBinaryTree(TreeNode root) {
		int res = 0;
		if (root == null) {
			return res;
		}

		Deque<NodePosition> dq = new ArrayDeque<>();
		dq.addLast(new NodePosition(root, 1));

		while (!dq.isEmpty()) {
			long left = dq.peekFirst().w;
			long right = dq.peekLast().w;
			res = Math.max(res, (int) (right - left + 1));
			int N = dq.size();

			for (int i = 0; i < N; i++) {
				NodePosition curr = dq.removeFirst();
				TreeNode node = curr.node;
				long w = curr.w - left;
				if (node.left != null) {
					dq.addLast(new NodePosition(node.left, 2 * w));
				}
				if (node.right != null) {
					dq.addLast(new NodePosition(node.right, 2 * w + 1));
				}
			}
		}

		return res;
	}

	private static class NodePosition {
		private final TreeNode node;
		private final long w;

		private NodePosition(TreeNode node, long w) {
			this.node = node;
			this.w = w;
		}
	}
}

import collections
from typing import List, Optional

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0
        if not root:
            return res

        dq = collections.deque([(root, 1)])

        while dq:
            left = dq[0][1]
            right = dq[-1][1]
            res = max(res, right - left + 1)
            for _ in range(len(dq)):
                node, w = dq.popleft()
                if node.left:
                    dq.append((node.left, 2*w))
                if node.right:
                    dq.append((node.right, 2*w+1))

        return res

863. All Nodes Distance K in Binary Tree

Record each node’s parent so every tree edge can be traversed in both directions. Then run BFS from target through its left child, right child, and parent. After exactly k levels, every node remaining in the deque is distance k from the target.

import java.util.*;

class Solution {
	public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
		Map<TreeNode, TreeNode> nodeToParent = new HashMap<>();
		recordParent(root, nodeToParent);

		Deque<TreeNode> dq = new ArrayDeque<>();
		dq.addLast(target);
		Set<TreeNode> seen = new HashSet<>();
		seen.add(target);

		while (!dq.isEmpty()) {
			if (k == 0) {
				List<Integer> res = new ArrayList<>();
				for (TreeNode node : dq) {
					res.add(node.val);
				}
				return res;
			}

			int N = dq.size();
			for (int i = 0; i < N; i++) {
				TreeNode node = dq.removeFirst();
				TreeNode[] nextNodes = {
					node.left,
					node.right,
					nodeToParent.get(node)
				};
				for (TreeNode nextNode : nextNodes) {
					if (nextNode != null && !seen.contains(nextNode)) {
						seen.add(nextNode);
						dq.addLast(nextNode);
					}
				}
			}
			k--;
		}

		return new ArrayList<>();
	}

	private void recordParent(TreeNode node, Map<TreeNode, TreeNode> nodeToParent) {
		if (node == null) {
			return;
		}

		if (node.left != null) {
			nodeToParent.put(node.left, node);
		}
		if (node.right != null) {
			nodeToParent.put(node.right, node);
		}

		recordParent(node.left, nodeToParent);
		recordParent(node.right, nodeToParent);
	}
}

import collections
from typing import List

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        node_to_parent = {}

        def recordParent(node):
            if not node:
                return

            if node.left:
                node_to_parent[node.left] = node
            if node.right:
                node_to_parent[node.right] = node

            recordParent(node.left)
            recordParent(node.right)

        recordParent(root)

        dq = collections.deque([target])
        seen = {target}

        while dq:
            if k == 0:
                return [n.val for n in dq]
            for _ in range(len(dq)):
                node = dq.popleft()
                for next_node in [node.left, node.right, node_to_parent.get(node, None)]:
                    if next_node and next_node not in seen:
                        seen.add(next_node)
                        dq.append(next_node)
            k -= 1

        return []

987. Vertical Order Traversal of a Binary Tree

Assign the root coordinate (0, 0), move left children to (row + 1, col - 1), and move right children to (row + 1, col + 1). Group (row, value) pairs by column, then sort each group by row and value before returning columns from left to right.

import java.util.*;

class Solution {
	public List<List<Integer>> verticalTraversal(TreeNode root) {
		List<List<Integer>> res = new ArrayList<>();
		if (root == null) {
			return res;
		}

		Map<Integer, List<int[]>> colToNums = new HashMap<>();
		Deque<NodePosition> dq = new ArrayDeque<>();
		dq.addLast(new NodePosition(root, 0, 0));
		int colMin = Integer.MAX_VALUE;
		int colMax = Integer.MIN_VALUE;

		while (!dq.isEmpty()) {
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				NodePosition curr = dq.removeFirst();
				TreeNode node = curr.node;
				int row = curr.row;
				int col = curr.col;
				colMin = Math.min(colMin, col);
				colMax = Math.max(colMax, col);
				colToNums.computeIfAbsent(
					col,
					key -> new ArrayList<>()
				).add(new int[] {row, node.val});
				if (node.left != null) {
					dq.addLast(new NodePosition(node.left, row + 1, col - 1));
				}
				if (node.right != null) {
					dq.addLast(new NodePosition(node.right, row + 1, col + 1));
				}
			}
		}

		for (int c = colMin; c <= colMax; c++) {
			List<int[]> nums = colToNums.get(c);
			nums.sort((a, b) -> {
				if (a[0] != b[0]) {
					return Integer.compare(a[0], b[0]);
				}
				return Integer.compare(a[1], b[1]);
			});

			List<Integer> values = new ArrayList<>();
			for (int[] pair : nums) {
				values.add(pair[1]);
			}
			res.add(values);
		}

		return res;
	}

	private static class NodePosition {
		private final TreeNode node;
		private final int row;
		private final int col;

		private NodePosition(TreeNode node, int row, int col) {
			this.node = node;
			this.row = row;
			this.col = col;
		}
	}
}

from collections import defaultdict, deque
from typing import List, Optional

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return []

        col_to_nums = defaultdict(list) # column to [(row, val)]
        dq = deque([(root, 0, 0)])
        col_min, col_max = float('inf'), float('-inf')

        while dq:
            for _ in range(len(dq)):
                node, row, col = dq.popleft()
                col_min = min(col_min, col)
                col_max = max(col_max, col)
                col_to_nums[col].append([row, node.val])
                if node.left:
                    dq.append((node.left, row + 1, col - 1))
                if node.right:
                    dq.append((node.right, row + 1, col + 1))

        for c in range(col_min, 1 + col_max):
            nums = col_to_nums[c]
            res.append([v for _, v in sorted(nums)])

        return res

1197. Minimum Knight Moves

Use symmetry to move the target into the first quadrant, then run BFS from (0, 0). Each level represents one knight move. Searching only from -2 through two positions beyond the target keeps the state space finite without excluding an optimal path.

import java.util.*;

class Solution {
	public int minKnightMoves(int x, int y) {
		x = Math.abs(x);
		y = Math.abs(y);
		int[][] jumps = {{2, 1}, {1, 2}, {-2, 1}, {-1, 2},
						 {2, -1}, {1, -2}, {-2, -1}, {-1, -2}};
		Deque<int[]> dq = new ArrayDeque<>();
		dq.add(new int[] {0, 0});
		Set<String> seen = new HashSet<>();
		seen.add("0,0");
		int steps = 0;

		while (true) {
			int L = dq.size();
			for (int i = 0; i < L; i++) {
				int[] curr = dq.pollFirst();
				int curr_x = curr[0];
				int curr_y = curr[1];
				if (curr_x == x && curr_y == y) {
					return steps;
				}
				for (int[] delta : jumps) {
					int next_x = curr_x + delta[0];
					int next_y = curr_y + delta[1];
					if (next_x < -2 || next_y < -2 ||
						next_x > x + 2 || next_y > y + 2) {
						continue;
					}
					int[] next = new int[] {next_x, next_y};
					String nextKey = String.valueOf(next_x) +
						"," + String.valueOf(next_y);
					if (!seen.contains(nextKey)) {
						seen.add(nextKey);
						dq.offerLast(next);
					}
				}
			}
			steps++;
		}
	}
}

import collections

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x = abs(x)
        y = abs(y)
        jumps = [(2, 1), (1, 2), (-2, 1), (-1, 2),
                 (2, -1), (1, -2), (-2, -1), (-1, -2)]
        dq = collections.deque([(0, 0)])
        seen = {(0, 0)}
        steps = 0

        while True:
            L = len(dq)
            for i in range(L):
                curr_x, curr_y = dq.popleft()
                if curr_x == x and curr_y == y:
                    return steps
                for delta_x, delta_y in jumps:
                    next_x = curr_x + delta_x
                    next_y = curr_y + delta_y
                    if next_x < -2 or next_y < -2 or next_x > x + 2 or next_y > y + 2:
                        continue
                    next = (next_x, next_y)
                    if next not in seen:
                        seen.add(next)
                        dq.append(next)
            steps += 1

994. Rotting Oranges

Enqueue all rotten oranges as simultaneous sources. Each BFS level represents one minute of spreading. Track fresh oranges so the algorithm can return -1 if some remain unreachable.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int orangesRotting(int[][] grid) {
		int R = grid.length;
		int C = grid[0].length;
		int fresh = 0;
		int rotton = 0;
		Deque<int[]> dq = new ArrayDeque<>();

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (grid[r][c] == 1) {
					fresh++;
				} else if (grid[r][c] == 2) {
					rotton++;
					dq.addLast(new int[] {r, c});
				}
			}
		}

		if (fresh == 0) {
			return 0;
		}

		if (rotton == 0) {
			return -1;
		}

		int time = 0;
		int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

		while (!dq.isEmpty()) {
			if (fresh == 0) {
				return time;
			}
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				int[] curr = dq.removeFirst();
				int curr_r = curr[0];
				int curr_c = curr[1];
				for (int[] dir : dirs) {
					int next_r = curr_r + dir[0];
					int next_c = curr_c + dir[1];
					if (next_r >= 0 && next_r < R &&
						next_c >= 0 && next_c < C &&
						grid[next_r][next_c] == 1) {
						grid[next_r][next_c] = 2;
						fresh--;
						rotton++;
						dq.addLast(new int[] {next_r, next_c});
					}
				}
			}
			time++;
		}

		return -1;
	}
}

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        R, C = len(grid), len(grid[0])
        fresh, rotton = 0, 0
        dq = deque()

        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1:
                    fresh += 1
                elif grid[r][c] == 2:
                    rotton += 1
                    dq.append((r, c))

        if fresh == 0:
            return 0

        if rotton == 0:
            return -1

        time = 0
        dirs = [(1, 0), (-1, 0), (0, 1),(0, -1)]

        while dq:
            if fresh == 0:
                return time
            for _ in range(len(dq)):
                curr_r, curr_c = dq.popleft()
                for dr, dc in dirs:
                    next_r, next_c = curr_r + dr, curr_c + dc
                    if 0 <= next_r < R and 0 <= next_c < C and grid[next_r][next_c] == 1:
                        grid[next_r][next_c] = 2
                        fresh -= 1
                        rotton += 1
                        dq.append((next_r, next_c))
            time += 1

        return -1

542. 01 Matrix

For every cell, compute the distance to the nearest zero. Start multi-source BFS from all zero cells and assign each unvisited one-cell a distance one greater than the cell that reaches it.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
	public int[][] updateMatrix(int[][] mat) {
		int R = mat.length;
		int C = mat[0].length;
		int[][] res = new int[R][C];
		Deque<int[]> dq = new ArrayDeque<>();

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (mat[r][c] == 0) {
					dq.addLast(new int[] {r, c});
				}
			}
		}

		int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		int dist = 1;
		while (!dq.isEmpty()) {
			int N = dq.size();
			for (int i = 0; i < N; i++) {
				int[] curr = dq.removeFirst();
				int curr_r = curr[0];
				int curr_c = curr[1];
				for (int[] dir : dirs) {
					int next_r = curr_r + dir[0];
					int next_c = curr_c + dir[1];
					if (next_r >= 0 && next_r < R &&
						next_c >= 0 && next_c < C &&
						mat[next_r][next_c] != 0) {
						mat[next_r][next_c] = 0;
						res[next_r][next_c] = dist;
						dq.addLast(new int[] {next_r, next_c});
					}
				}
			}
			dist++;
		}

		return res;
	}
}

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        R, C = len(mat), len(mat[0])
        res = [[0]*C for _ in range(R)]
        dq = deque()
        for r in range(R):
            for c in range(C):
                if mat[r][c] == 0:
                    dq.append((r,c))

        dirs = [(1, 0), (-1, 0), (0, 1),(0, -1)]
        dist = 1
        while dq:
            for _ in range(len(dq)):
                curr_r, curr_c = dq.popleft()
                for dr, dc in dirs:
                    next_r, next_c = curr_r+dr, curr_c+dc
                    if 0 <= next_r <R and 0 <= next_c < C and mat[next_r][next_c] != 0:
                        mat[next_r][next_c] = 0
                        res[next_r][next_c] = dist
                        dq.append((next_r, next_c))
            dist += 1

        return res

815. Bus Routes

Treat each bus route as a BFS state. Build a stop-to-routes map, initialize the queue with every bus available at source, and let each BFS level represent one more bus taken. Track visited buses to avoid boarding one twice and visited stops to avoid repeatedly expanding the same transfer point.

import java.util.*;

class Solution {
	public int numBusesToDestination(int[][] routes, int source, int target) {
		if (source == target) {
			return 0;
		}

		Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
		for (int routeId = 0; routeId < routes.length; routeId++) {
			for (int stop : routes[routeId]) {
				stopToRoutes.computeIfAbsent(
					stop,
					key -> new ArrayList<>()
				).add(routeId);
			}
		}

		Set<Integer> visitedBuses = new HashSet<>();
		Set<Integer> visitedStops = new HashSet<>();
		visitedStops.add(source);
		Queue<Integer> queue = new ArrayDeque<>();

		// Initialize BFS with buses reachable from source
		for (int bus : stopToRoutes.getOrDefault(source, List.of())) {
			queue.offer(bus);
			visitedBuses.add(bus);
		}

		int busesTaken = 1;

		while (!queue.isEmpty()) {
			for (int size = queue.size(); size > 0; size--) {
				int bus = queue.poll();

				// If this bus reaches target, we're done
				if (containsStop(routes[bus], target)) {
					return busesTaken;
				}

				// Explore all stops this bus visits
				for (int stop : routes[bus]) {
					if (!visitedStops.contains(stop)) {
						// Must be placed here, not in the for loop.
						visitedStops.add(stop);
						for (int nextBus : stopToRoutes.get(stop)) {
							if (!visitedBuses.contains(nextBus)) {
								visitedBuses.add(nextBus);
								queue.offer(nextBus);
							}
						}
					}
				}
			}

			busesTaken++;
		}

		return -1;
	}

	private boolean containsStop(int[] route, int target) {
		for (int stop : route) {
			if (stop == target) {
				return true;
			}
		}
		return false;
	}
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0

        # Need to revisit and carefully think about complexity
        # Map each stop to the buses that visit it
        stop_to_routes = defaultdict(list)
        for route_id, route in enumerate(routes):
            for stop in route:
                stop_to_routes[stop].append(route_id)

        visited_buses = set()
        visited_stops = set()
        visited_stops.add(source)
        queue = deque()

        # Initialize BFS with buses reachable from source
        for bus in stop_to_routes[source]:
            queue.append(bus)
            visited_buses.add(bus)

        buses_taken = 1

        while queue:
            for _ in range(len(queue)):
                bus = queue.popleft()

                # If this bus reaches target, we're done
                if target in routes[bus]:
                    return buses_taken

                # Explore all stops this bus visits
                for stop in routes[bus]:
                    if stop not in visited_stops:
                        # Must be placed here, not in the for loop.
                        visited_stops.add(stop)
                        for next_bus in stop_to_routes[stop]:
                            if next_bus not in visited_buses:
                                visited_buses.add(next_bus)
                                queue.append(next_bus)

            buses_taken += 1

        return -1

127. Word Ladder

Build wildcard patterns such as h*t to connect words that differ by one character. Each word is a graph state, and all words sharing one of its patterns are neighbors. BFS through that implicit adjacency map returns the shortest transformation length.

import java.util.*;

class Solution {
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (!wordList.contains(endWord)) {
			return 0;
		}

		int L = beginWord.length();

		if (!wordList.contains(beginWord)) {
			wordList.add(beginWord);
		}

		Map<String, List<String>> patternToWords = new HashMap<>();
		// O(NL^2) for building patterns, can be much smaller for O(N^2L)
		// Graph building is the bottle neck, not BFS
		for (String word : wordList) {
			for (int i = 0; i < L; i++) {
				// key line to memorize
				String pattern = word.substring(0, i) +
					"*" + word.substring(i + 1);
				patternToWords.computeIfAbsent(
					pattern,
					key -> new ArrayList<>()
				).add(word);
			}
		}

		Queue<String> q = new ArrayDeque<>();
		q.offer(beginWord);
		Set<String> seen = new HashSet<>();
		seen.add(beginWord);
		int steps = 1;

		// O(NL^2) for BFS, alternative solution would be O(N + E)
		while (!q.isEmpty()) {
			for (int size = q.size(); size > 0; size--) {
				String word = q.poll();
				if (word.equals(endWord)) {
					return steps;
				}

				for (int i = 0; i < L; i++) {
					String pattern = word.substring(0, i) +
						"*" + word.substring(i + 1);

					for (String nei : patternToWords.get(pattern)) {
						if (!seen.contains(nei)) {
							seen.add(nei);
							q.offer(nei);
						}
					}
				}
			}

			steps++;
		}

		return 0;
	}
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        L = len(beginWord)

        if beginWord not in wordList:
            wordList.append(beginWord)

        pattern_to_words = defaultdict(list)
        # O(NL^2) for building patterns, can be much smaller for O(N^2L)
        # Graph building is the bottle neck, not BFS
        for word in wordList:
            for i in range(L):
                # key line to memorize
                pattern = word[:i] + "*" + word[i + 1:]
                pattern_to_words[pattern].append(word)

        q = deque([beginWord])
        seen = {beginWord}
        steps = 1

        # O(NL^2) for BFS, alternative solution would be O(N + E)
        while q:
            for _ in range(len(q)):
                word = q.popleft()

                if word == endWord:
                    return steps

                for i in range(L):
                    pattern = word[:i] + "*" + word[i + 1:]

                    for nei in pattern_to_words[pattern]:
                        if nei not in seen:
                            seen.add(nei)
                            q.append(nei)

            steps += 1

        return 0