1. Island Perimeter
Easy · LC 463
Given a grid of 1s for land and 0s for water containing exactly one island, return the island's perimeter. Scan all cells; each land cell adds 4, then subtract 2 for each land neighbor above or to its left, since both cells share that edge. Counting only already-seen neighbors avoids double subtraction; equivalently, add 1 for every side facing water or the grid border.
def island_perimeter(grid: list[list[int]]) -> int:
"""LC 463. Island Perimeter.
Every land cell contributes 4 sides, and each pair of adjacent land
cells hides one side on BOTH cells, so subtract 2 per shared edge.
Looking only up and left means each shared edge is seen from exactly
one of its two cells, so nothing is subtracted twice. O(mn) time,
O(1) space.
"""
perimeter = 0
for r, row in enumerate(grid):
for c, cell in enumerate(row):
if not cell:
continue
perimeter += 4
if r > 0 and grid[r - 1][c]:
perimeter -= 2 # edge shared with the already-seen cell above
if c > 0 and grid[r][c - 1]:
perimeter -= 2 # edge shared with the already-seen cell to the left
return perimeter
// LC 463. One pass: each land cell contributes 4, minus 2 for each land
// neighbor ABOVE or to its LEFT, since the shared edge was counted once from
// each side and only already-seen neighbors avoid double subtraction.
// (Equivalently: +1 for every side facing water or the grid border.)
int islandPerimeter(vector<vector<int>> grid) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
int perimeter = 0;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) {
if (grid[r][c] != 1) continue;
perimeter += 4;
if (r > 0 && grid[r - 1][c] == 1) perimeter -= 2; // shared edge with cell above
if (c > 0 && grid[r][c - 1] == 1) perimeter -= 2; // shared edge with cell left
}
return perimeter;
}
/// LC 463. No traversal needed: every land cell adds 4, then subtract 2 per
/// land neighbor above or to the left -- counting only already-seen neighbors
/// charges each shared edge exactly once.
pub fn island_perimeter(grid: Vec<Vec<i32>>) -> i32 {
let mut perimeter = 0;
for r in 0..grid.len() {
for c in 0..grid[0].len() {
if grid[r][c] == 1 {
perimeter += 4;
if r > 0 && grid[r - 1][c] == 1 {
perimeter -= 2;
}
if c > 0 && grid[r][c - 1] == 1 {
perimeter -= 2;
}
}
}
}
perimeter
}
/** LC 463. Each land cell adds 4, minus 2 per land neighbor above or left: only already-seen neighbors, so each shared edge is subtracted once. */
export function islandPerimeter(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
let perimeter = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== 1) continue;
perimeter += 4;
if (r > 0 && grid[r - 1][c] === 1) perimeter -= 2; // shared edge with the cell above
if (c > 0 && grid[r][c - 1] === 1) perimeter -= 2; // shared edge with the cell to the left
}
}
return perimeter;
}
// LC 463. Each land cell contributes 4 sides, and each land neighbor ABOVE or
// to the LEFT hides one shared edge on both cells, so subtract 2 per pair.
func islandPerimeter(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
perimeter := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] != 1 {
continue
}
perimeter += 4
if r > 0 && grid[r-1][c] == 1 {
perimeter -= 2 // shared edge with the already-seen cell above
}
if c > 0 && grid[r][c-1] == 1 {
perimeter -= 2 // shared edge with the already-seen cell left
}
}
}
return perimeter
}
// LC 463. Each land cell adds 4; subtract 2 per land neighbor above or to the
// left, so every shared edge is removed exactly once.
func islandPerimeter(_ grid: [[Int]]) -> Int {
let rows = grid.count, cols = grid[0].count
var perimeter = 0
for r in 0..<rows {
for c in 0..<cols {
if grid[r][c] != 1 { continue }
perimeter += 4
if r > 0 && grid[r - 1][c] == 1 { perimeter -= 2 } // shared edge with cell above
if c > 0 && grid[r][c - 1] == 1 { perimeter -= 2 } // shared edge with cell left
}
}
return perimeter
}
2. Verifying An Alien Dictionary
Easy · LC 953
Given an alien alphabet order and a list of words, decide whether the words are sorted lexicographically under that order. Build a map from each character to its rank, then compare every adjacent pair of words at their first differing character. The edge case is a pair with no differing character: the longer word must not come first, because a prefix sorts before its extension.
def is_alien_sorted(words: list[str], order: str) -> bool:
"""LC 953. Verifying an Alien Dictionary.
Map each letter to its rank in the alien order, then check every
ADJACENT pair of words: the first differing character decides, and
its ranks must not decrease. The trap is a pair with no differing
character -- "apple" before "app" is invalid because a prefix must
sort before its extension. O(total characters) time, O(1) space.
"""
rank = {ch: i for i, ch in enumerate(order)}
def in_order(first: str, second: str) -> bool:
for a, b in zip(first, second):
if a != b:
return rank[a] < rank[b] # first difference decides everything
# no difference within the overlap: shorter (the prefix) must come first
return len(first) <= len(second)
return all(in_order(words[i], words[i + 1]) for i in range(len(words) - 1))
// LC 953. Map each character to its rank in the alien order, then compare
// every ADJACENT pair at their first differing character. The prefix trap is
// a pair with no differing character: the longer word must not come first,
// because a prefix sorts before its extension ("app" < "apple", always).
bool isAlienSorted(vector<string> words, string order) {
int rank[26];
for (int i = 0; i < 26; ++i) rank[order[i] - 'a'] = i;
for (size_t w = 1; w < words.size(); ++w) {
const string& a = words[w - 1];
const string& b = words[w];
size_t i = 0;
while (i < a.size() && i < b.size() && a[i] == b[i]) ++i;
if (i == a.size() || i == b.size()) {
if (a.size() > b.size()) return false; // prefix trap: extension before prefix
} else if (rank[a[i] - 'a'] > rank[b[i] - 'a']) {
return false;
}
}
return true;
}
/// LC 953. Map each letter to its rank, compare adjacent words at the first
/// differing letter. The prefix trap: with no differing letter the longer
/// word must NOT come first, because a prefix sorts before its extension.
pub fn is_alien_sorted(words: Vec<String>, order: String) -> bool {
let mut rank = [0u8; 26];
for (i, b) in order.bytes().enumerate() {
rank[(b - b'a') as usize] = i as u8;
}
words.windows(2).all(|pair| {
let (a, b) = (pair[0].as_bytes(), pair[1].as_bytes());
for (&x, &y) in a.iter().zip(b.iter()) {
if x != y {
return rank[(x - b'a') as usize] < rank[(y - b'a') as usize];
}
}
a.len() <= b.len() // prefix trap: "apple" before "app" is unsorted
})
}
/** LC 953. Rank map + adjacent pairs compared at the first differing char; the prefix trap: no differing char means the longer word must not come first. */
export function isAlienSorted(words: string[], order: string): boolean {
const rank = new Map<string, number>();
for (let i = 0; i < order.length; i++) rank.set(order[i], i);
function inOrder(a: string, b: string): boolean {
const len = Math.min(a.length, b.length);
for (let i = 0; i < len; i++) {
if (a[i] !== b[i]) return rank.get(a[i])! < rank.get(b[i])!;
}
return a.length <= b.length; // a prefix sorts before its extension
}
for (let i = 1; i < words.length; i++) {
if (!inOrder(words[i - 1], words[i])) return false;
}
return true;
}
// LC 953. Rank map + adjacent pairs: the first differing character decides;
// a pair with NO differing character is the prefix trap (extension before prefix).
func isAlienSorted(words []string, order string) bool {
var rank [26]int
for i := 0; i < 26; i++ {
rank[order[i]-'a'] = i
}
for w := 1; w < len(words); w++ {
a, b := words[w-1], words[w]
i := 0
for i < len(a) && i < len(b) && a[i] == b[i] {
i++
}
if i == len(a) || i == len(b) {
if len(a) > len(b) {
return false // prefix trap: extension before prefix
}
} else if rank[a[i]-'a'] > rank[b[i]-'a'] {
return false
}
}
return true
}
// LC 953. Rank map over the alien order, then compare adjacent word pairs at
// their first differing letter; no difference means the prefix must come first.
func isAlienSorted(_ words: [String], _ order: String) -> Bool {
var rank = [Int](repeating: 0, count: 26)
for (i, ch) in order.utf8.enumerated() { rank[Int(ch) - 97] = i }
let codes = words.map { $0.utf8.map { Int($0) - 97 } }
for w in 1..<codes.count {
let a = codes[w - 1], b = codes[w]
var i = 0
while i < a.count && i < b.count && a[i] == b[i] { i += 1 }
if i == a.count || i == b.count {
if a.count > b.count { return false } // prefix trap: extension before prefix
} else if rank[a[i]] > rank[b[i]] {
return false
}
}
return true
}
3. Find the Town Judge
Easy · LC 997
Given n people and trust pairs meaning a trusts b, return the town judge, who trusts nobody and is trusted by everyone else, or -1. Track a single score per person, subtracting one for each outgoing trust and adding one for each incoming trust. The judge is the unique person scoring exactly n-1, since any outgoing trust ruins the total; no adjacency structure is needed.
def find_judge(n: int, trust: list[list[int]]) -> int:
"""LC 997. Find the Town Judge.
One score per person: +1 per incoming trust, -1 per outgoing one,
i.e. indegree minus outdegree. The judge is trusted by all n-1
others and trusts nobody, so they score exactly n-1 -- and a single
outgoing trust makes that total unreachable, so no adjacency
structure is needed. O(n + len(trust)) time, O(n) space.
"""
score = [0] * (n + 1) # people are 1-indexed; slot 0 stays unused
for truster, trusted in trust:
score[truster] -= 1
score[trusted] += 1
for person in range(1, n + 1):
if score[person] == n - 1:
return person
return -1
// LC 997. No adjacency structure needed: one net score per person, -1 per
// outgoing trust and +1 per incoming. The judge is the unique person scoring
// exactly n-1, since any outgoing trust ruins the total and all n-1 others
// must trust them.
int findJudge(int n, vector<vector<int>> trust) {
vector<int> score(n + 1, 0);
for (const auto& t : trust) {
--score[t[0]]; // t[0] trusts someone: disqualifying
++score[t[1]]; // t[1] gains a truster
}
for (int person = 1; person <= n; ++person)
if (score[person] == n - 1) return person;
return -1;
}
/// LC 997. One score per person: -1 per outgoing trust, +1 per incoming.
/// The judge is the unique score of n - 1; any outgoing trust ruins it, so
/// no adjacency structure is needed.
pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
let mut score = vec![0i32; n as usize + 1];
for t in &trust {
score[t[0] as usize] -= 1;
score[t[1] as usize] += 1;
}
(1..=n).find(|&person| score[person as usize] == n - 1).unwrap_or(-1)
}
/** LC 997. One score per person: -1 per outgoing trust, +1 per incoming; the judge is the unique score of n-1, since any outgoing trust ruins it. */
export function findJudge(n: number, trust: number[][]): number {
const score = new Array<number>(n + 1).fill(0);
for (const [a, b] of trust) {
score[a]--;
score[b]++;
}
for (let person = 1; person <= n; person++) {
if (score[person] === n - 1) return person;
}
return -1;
}
// LC 997. Trust score per person: indegree minus outdegree; the judge is the
// unique person scoring exactly n-1, so no adjacency structure is needed.
func findJudge(n int, trust [][]int) int {
score := make([]int, n+1) // people are 1-indexed; slot 0 stays unused
for _, t := range trust {
score[t[0]]-- // t[0] trusts someone: disqualifying
score[t[1]]++ // t[1] gains a truster
}
for person := 1; person <= n; person++ {
if score[person] == n-1 {
return person
}
}
return -1
}
// LC 997. Trust score per person: indegree minus outdegree; the judge is the
// unique person scoring exactly n-1, so no adjacency structure is needed.
func findJudge(_ n: Int, _ trust: [[Int]]) -> Int {
var score = [Int](repeating: 0, count: n + 1) // people are 1-indexed
for t in trust {
score[t[0]] -= 1 // t[0] trusts someone: disqualifying
score[t[1]] += 1 // t[1] gains a truster
}
for person in 1...n where score[person] == n - 1 { return person }
return -1
}
4. Number of Islands
Medium · LC 200
Given a 2D grid of 1s for land and 0s for water, count the islands formed by 4-directionally connected land. Scan the grid, and at each unvisited land cell launch a flood fill, DFS or BFS, that sinks the whole component by overwriting its cells. The number of launches equals the number of islands; marking cells during the fill stops one island from being counted twice.
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
}
5. Max Area of Island
Medium · LC 695
Given a grid of 0s and 1s, return the area of the largest 4-connected island, or 0 if there is none. Run the Number of Islands scan, but make the flood fill return how many cells it sank, taking the maximum over all launches. Recursively each cell returns 1 plus its four neighbor calls, with visited cells zeroed first so nothing is counted twice.
def max_area_of_island(grid: list[list[int]]) -> int:
"""LC 695. Max Area of Island.
Number of Islands with a return value: scan the grid and flood-fill
every land cell, but make the fill RETURN how many cells it sank --
1 for the current cell plus the four neighbor calls. Zeroing a cell
before recursing is the visited mark. O(mn) time, O(mn) stack in
the worst case.
"""
rows, cols = len(grid), len(grid[0])
def sink(r: int, c: int) -> int:
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == 0:
return 0
grid[r][c] = 0 # sink BEFORE recursing so no cell is ever counted twice
return 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1)
return max(sink(r, c) for r in range(rows) for c in range(cols))
// LC 695. The Number of Islands scan, but the flood fill RETURNS the area it
// sank: each cell zeroes itself first (the visited mark) and reports 1 plus
// its four neighbor calls; the answer is the max over all launches.
int maxAreaOfIsland(vector<vector<int>> grid) {
int rows = static_cast<int>(grid.size()), cols = static_cast<int>(grid[0].size());
auto sink = [&](auto&& self, int r, int c) -> int {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1) return 0;
grid[r][c] = 0; // zero BEFORE recursing so nothing is counted twice
return 1 + self(self, r + 1, c) + self(self, r - 1, c) + self(self, r, c + 1) +
self(self, r, c - 1);
};
int best = 0;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c)
if (grid[r][c] == 1) best = max(best, sink(sink, r, c));
return best;
}
/// LC 695. Number of Islands scan, but the flood fill returns how many cells
/// it sank: each cell is 1 plus its four neighbor calls, zeroed first so
/// nothing is counted twice.
pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 {
fn sink(grid: &mut Vec<Vec<i32>>, r: usize, c: usize) -> i32 {
if r >= grid.len() || c >= grid[0].len() || grid[r][c] != 1 {
return 0;
}
grid[r][c] = 0;
1 + 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 best = 0;
for r in 0..grid.len() {
for c in 0..grid[0].len() {
if grid[r][c] == 1 {
best = best.max(sink(&mut grid, r, c));
}
}
}
best
}
/** LC 695. The Number of Islands flood fill, except each sink call RETURNS the area it consumed. */
export function maxAreaOfIsland(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
function sink(r: number, c: number): number {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return 0;
grid[r][c] = 0; // zero first so nothing is counted twice
return 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1);
}
let best = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1) best = Math.max(best, sink(r, c));
}
}
return best;
}
// LC 695. Flood fill that RETURNS the area it sank: zero the cell before
// recursing (the visited mark) and report 1 plus the four neighbor calls.
func maxAreaOfIsland(grid [][]int) int {
rows, cols := len(grid), len(grid[0])
var sink func(r, c int) int
sink = func(r, c int) int {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1 {
return 0
}
grid[r][c] = 0 // zero BEFORE recursing so nothing is counted twice
return 1 + sink(r+1, c) + sink(r-1, c) + sink(r, c+1) + sink(r, c-1)
}
best := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if area := sink(r, c); area > best {
best = area
}
}
}
return best
}
// LC 695. Flood fill that RETURNS the area it sank: zero each cell before
// recursing so nothing is counted twice; the answer is the max over launches.
func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
var grid = grid
let rows = grid.count, cols = grid[0].count
func sink(_ r: Int, _ c: Int) -> Int {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != 1 { return 0 }
grid[r][c] = 0 // zero BEFORE recursing so no cell is ever counted twice
return 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1)
}
var best = 0
for r in 0..<rows {
for c in 0..<cols where grid[r][c] == 1 {
best = max(best, sink(r, c))
}
}
return best
}
6. Clone Graph
Medium · LC 133
Given a reference to one node of a connected undirected graph, return a deep copy of the entire graph. DFS or BFS from the start node, keeping a hash map from each original node to its clone, creating clones on first visit and wiring neighbor lists from mapped entries. The map doubles as the visited set; checking it before recursing is what keeps cycles from looping forever.
def clone_graph(adj_list: list[list[int]]) -> list[list[int]]:
"""LC 133. Clone Graph.
On LeetCode the function receives one Node pointer of a connected
undirected graph and the map runs old Node -> cloned Node; here the
graph arrives as the judge's adjacency list of 1-indexed values, so
the map runs old value -> cloned Node instead. DFS from node 1,
creating each clone on FIRST visit and wiring neighbor lists from
mapped entries -- the map doubles as the visited set, which is what
keeps cycles from recursing forever. O(V + E) time and space.
"""
class Node:
def __init__(self, val: int):
self.val = val
self.neighbors: list["Node"] = []
if not adj_list:
return []
old_to_clone: dict[int, Node] = {}
def clone(val: int) -> Node:
if val in old_to_clone:
return old_to_clone[val] # already cloned: reuse, don't recurse
copy = Node(val)
old_to_clone[val] = copy # register BEFORE wiring neighbors, or cycles loop
for neighbor_val in adj_list[val - 1]: # node values are 1-indexed
copy.neighbors.append(clone(neighbor_val))
return copy
clone(1) # the graph is connected, so node 1 reaches everything
return [
[neighbor.val for neighbor in old_to_clone[val].neighbors]
for val in range(1, len(adj_list) + 1)
]
// LC 133. LeetCode's version hands you a Node* and wants a deep copy; the
// whole trick is a hash map original -> clone that doubles as the visited
// set: create each clone on FIRST visit -- mapping it BEFORE recursing, or
// cycles loop forever -- and wire neighbor lists from mapped entries. The
// graph arrives here as a 1-indexed adjacency list, so we build real nodes,
// run exactly that pointer-keyed DFS, and serialize the copy back out.
vector<vector<int>> cloneGraph(vector<vector<int>> adjList) {
int n = static_cast<int>(adjList.size());
if (n == 0) return {};
struct Node {
int val;
vector<Node*> neighbors;
};
vector<Node> original(n + 1); // 1-indexed, matching LeetCode's labels
for (int v = 1; v <= n; ++v) {
original[v].val = v;
for (int u : adjList[v - 1]) original[v].neighbors.push_back(&original[u]);
}
deque<Node> pool; // owns the cloned nodes (stable addresses)
unordered_map<Node*, Node*> clone; // original -> copy, and the visited set
auto dfs = [&](auto&& self, Node* node) -> Node* {
auto found = clone.find(node);
if (found != clone.end()) return found->second;
pool.push_back({node->val, {}});
Node* copy = &pool.back();
clone[node] = copy; // map before recursing: this is the cycle guard
for (Node* next : node->neighbors) copy->neighbors.push_back(self(self, next));
return copy;
};
Node* start = dfs(dfs, &original[1]);
vector<vector<int>> ans(n); // read the answer off the COPY, never the input
vector<bool> seen(n + 1, false);
queue<Node*> q;
q.push(start);
seen[start->val] = true;
while (!q.empty()) {
Node* node = q.front();
q.pop();
for (Node* next : node->neighbors) {
ans[node->val - 1].push_back(next->val);
if (!seen[next->val]) {
seen[next->val] = true;
q.push(next);
}
}
}
return ans;
}
/// LC 133. The pointer version BFS/DFSes from the start node with a hash map
/// from each original Node to its clone, creating clones on first visit and
/// wiring neighbor lists from mapped entries; the map doubles as the visited
/// set, which is what keeps cycles from looping forever. This Rust version
/// maps node index to clone index the same way over the 1-indexed adjacency
/// lists, because Rc/RefCell cycles cannot express this undirected graph
/// safely (an Rc cycle leaks, and a Weak back-edge cannot be told apart from
/// a forward edge here).
pub fn clone_graph(adj_list: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = adj_list.len();
if n == 0 {
return Vec::new();
}
let mut clone = vec![Vec::new(); n];
let mut visited = vec![false; n]; // visited[orig] = clone already created
let mut queue = VecDeque::from([0usize]);
visited[0] = true;
while let Some(u) = queue.pop_front() {
for &v in &adj_list[u] {
clone[u].push(v); // wire the clone's edge from the mapped entry
let v = (v - 1) as usize;
if !visited[v] {
visited[v] = true;
queue.push_back(v);
}
}
}
clone
}
/**
* LC 133, expressed over LeetCode's serialized form: adjList[i] lists the
* 1-indexed neighbors of node i+1, and the deep copy is returned the same way.
* LeetCode's actual pointer version maps Node to clone identically: DFS with a
* Map from each original node to its clone, creating the clone on first visit
* and wiring neighbor lists from mapped entries. The map doubles as the
* visited set, which is what keeps cycles from looping forever.
*/
export function cloneGraph(adjList: number[][]): number[][] {
if (adjList.length === 0) return [];
class GraphNode {
val: number;
neighbors: GraphNode[] = [];
constructor(val: number) {
this.val = val;
}
}
// Rebuild the pointer graph the serialized form describes.
const original: GraphNode[] = adjList.map((_, i) => new GraphNode(i + 1));
for (let i = 0; i < adjList.length; i++) {
for (const nb of adjList[i]) original[i].neighbors.push(original[nb - 1]);
}
// The real LC 133 algorithm, given only a reference to node 1.
const cloneOf = new Map<GraphNode, GraphNode>();
function clone(node: GraphNode): GraphNode {
const seen = cloneOf.get(node);
if (seen) return seen;
const copy = new GraphNode(node.val);
cloneOf.set(node, copy); // register BEFORE recursing or cycles never end
for (const nb of node.neighbors) copy.neighbors.push(clone(nb));
return copy;
}
const start = clone(original[0]);
// Serialize the clone back to an adjacency list (the graph is connected).
const cloned: number[][] = adjList.map(() => []);
const visited = new Set<GraphNode>([start]);
const stack: GraphNode[] = [start];
while (stack.length > 0) {
const node = stack.pop()!;
cloned[node.val - 1] = node.neighbors.map((nb) => nb.val);
for (const nb of node.neighbors) {
if (!visited.has(nb)) {
visited.add(nb);
stack.push(nb);
}
}
}
return cloned;
}
// LC 133. DFS from the seed; the map original -> clone doubles as the visited
// set, and registering the copy BEFORE wiring neighbors keeps cycles finite.
func cloneGraph(graph *Node) *Node {
if graph == nil {
return nil
}
clones := map[*Node]*Node{}
var clone func(node *Node) *Node
clone = func(node *Node) *Node {
if cp, ok := clones[node]; ok {
return cp // already cloned: reuse, don't recurse
}
cp := &Node{Val: node.Val}
clones[node] = cp // map before recursing: this is the cycle guard
for _, next := range node.Neighbors {
cp.Neighbors = append(cp.Neighbors, clone(next))
}
return cp
}
return clone(graph)
}
// LC 133. DFS with a map original -> clone that doubles as the visited set:
// register each clone BEFORE wiring neighbors, or cycles recurse forever.
func cloneGraph(_ adjList: [[Int]]) -> [[Int]] {
let n = adjList.count
if n == 0 { return [] }
let original = (0...n).map { Node($0) } // 1-indexed, matching LeetCode's labels
for v in 1...n {
for u in adjList[v - 1] { original[v].neighbors.append(original[u]) }
}
var clone: [ObjectIdentifier: Node] = [:] // original -> copy, and the visited set
func dfs(_ node: Node) -> Node {
if let copy = clone[ObjectIdentifier(node)] { return copy }
let copy = Node(node.val)
clone[ObjectIdentifier(node)] = copy // map before recursing: the cycle guard
for next in node.neighbors { copy.neighbors.append(dfs(next)) }
return copy
}
let start = dfs(original[1]) // the graph is connected: node 1 reaches everything
var ans = [[Int]](repeating: [], count: n) // read the answer off the COPY
var seen = [Bool](repeating: false, count: n + 1)
var queue = [start]
var head = 0
seen[start.val] = true
while head < queue.count {
let node = queue[head]
head += 1
for next in node.neighbors {
ans[node.val - 1].append(next.val)
if !seen[next.val] {
seen[next.val] = true
queue.append(next)
}
}
}
return ans
}
7. Walls And Gates
Medium · LC 286
Given a grid of gates, walls, and empty rooms marked infinity, fill each room with the distance to its nearest gate, in place. Seed one queue with every gate and run a single BFS outward, writing the distance on first arrival and stepping only into rooms still holding infinity. Multi-source BFS works because all sources expand in lockstep, so the first arrival at any room comes from the nearest gate.
def walls_and_gates(rooms: list[list[int]]) -> None:
"""LC 286. Walls and Gates.
Multi-source BFS: seed one queue with EVERY gate at distance 0,
then expand outward writing distances in place, stepping only into
rooms still holding INF. All wavefronts advance in lockstep, so the
first arrival at any room comes from its nearest gate. Mutates the
grid; returns None. O(mn) time and space.
"""
INF = 2**31 - 1 # the problem's marker for an empty, unfilled room
rows, cols = len(rooms), len(rooms[0])
queue = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0)
while 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 rooms[nr][nc] == INF:
rooms[nr][nc] = rooms[r][c] + 1 # first arrival = nearest gate
queue.append((nr, nc))
// LC 286. Multi-source BFS, in place: seed ONE queue with every gate (0) and
// expand all sources in lockstep, stepping only into rooms still holding
// INT_MAX and writing distance on first arrival. Lockstep expansion is why
// it works -- the first wave to reach a room necessarily came from its
// nearest gate. Walls (-1) and gates are never overwritten.
void wallsAndGates(vector<vector<int>>& rooms) {
int rows = static_cast<int>(rooms.size()), cols = static_cast<int>(rooms[0].size());
queue<pair<int, int>> q;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c)
if (rooms[r][c] == 0) q.push({r, c});
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!q.empty()) {
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 && rooms[nr][nc] == INT_MAX) {
rooms[nr][nc] = rooms[r][c] + 1; // first arrival = nearest gate
q.push({nr, nc});
}
}
}
}
/// LC 286. Multi-source BFS: seed one queue with every gate and expand in
/// lockstep, stepping only into rooms still holding i32::MAX. First arrival
/// at any room is therefore from its nearest gate.
pub fn walls_and_gates(rooms: &mut Vec<Vec<i32>>) {
let (rows, cols) = (rooms.len(), rooms[0].len());
let mut queue = VecDeque::new();
for r in 0..rows {
for c in 0..cols {
if rooms[r][c] == 0 {
queue.push_back((r, c));
}
}
}
while let Some((r, c)) = queue.pop_front() {
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 && rooms[nr][nc] == i32::MAX {
rooms[nr][nc] = rooms[r][c] + 1;
queue.push_back((nr, nc));
}
}
}
}
/** LC 286. Multi-source BFS seeded with every gate; lockstep expansion means the first arrival at a room came from its nearest gate. */
export function wallsAndGates(rooms: number[][]): void {
const INF = 2147483647;
const rows = rooms.length;
const cols = rooms[0].length;
const queue: [number, number][] = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (rooms[r][c] === 0) queue.push([r, c]);
}
}
let head = 0; // O(1) dequeue without shift()
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [dr, dc] of FOUR_DIRECTIONS) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] === INF) {
rooms[nr][nc] = rooms[r][c] + 1; // writing the distance doubles as the visited mark
queue.push([nr, nc]);
}
}
}
}
// LC 286. Multi-source BFS seeded with EVERY gate at once; lockstep wavefronts
// mean the first arrival at any room came from its nearest gate.
func wallsAndGates(rooms [][]int) {
const inf = 1<<31 - 1 // the problem's marker for an empty, unfilled room
rows, cols := len(rooms), len(rooms[0])
queue := [][2]int{}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if rooms[r][c] == 0 {
queue = append(queue, [2]int{r, c})
}
}
}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
r, c := cell[0], cell[1]
for _, d := range [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && rooms[nr][nc] == inf {
rooms[nr][nc] = rooms[r][c] + 1 // first arrival = nearest gate
queue = append(queue, [2]int{nr, nc})
}
}
}
}
// LC 286. Multi-source BFS: seed ONE queue with every gate at distance 0 and
// expand in lockstep, so the first arrival at any room comes from its nearest gate.
func wallsAndGates(_ rooms: inout [[Int]]) {
let inf = 2147483647 // the problem's marker for an empty, unfilled room
let rows = rooms.count, cols = rooms[0].count
var queue: [(Int, Int)] = []
for r in 0..<rows {
for c in 0..<cols where rooms[r][c] == 0 { queue.append((r, c)) }
}
var head = 0
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
while head < queue.count {
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 && rooms[nr][nc] == inf {
rooms[nr][nc] = rooms[r][c] + 1 // first arrival = nearest gate
queue.append((nr, nc))
}
}
}
}
8. Rotting Oranges
Medium · LC 994
Given a grid of empty cells, fresh oranges, and rotten oranges that rot adjacent fresh ones each minute, return the minutes until no fresh orange remains, or -1. Seed a queue with all initially rotten oranges and BFS in level-sized rounds, counting one minute per round while decrementing a fresh counter. Watch two pitfalls: return -1 if any fresh orange stays unreachable, and avoid counting an extra minute after the final round.
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
}
9. Pacific Atlantic Water Flow
Medium · LC 417
Given a height matrix where water flows to equal-or-lower neighbors, return cells able to reach both the Pacific along the top and left edges and the Atlantic along the bottom and right edges. Search inward from each ocean's border cells, moving only to equal-or-higher neighbors, and record each ocean's reachable set. The answer is the intersection of the two sets; reversing the flow avoids simulating from every cell.
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
"""LC 417. Pacific Atlantic Water Flow.
Reverse the flow: instead of simulating drainage from every cell,
DFS inland from each ocean's border moving only to equal-or-HIGHER
neighbors, collecting each ocean's reachable set. Cells in BOTH
sets drain to both oceans, so the answer is the intersection -- two
sweeps instead of mn simulations. O(mn) time and space.
"""
rows, cols = len(heights), len(heights[0])
def climb(r: int, c: int, reached: set) -> None:
reached.add((r, c))
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 (nr, nc) not in reached
and heights[nr][nc] >= heights[r][c] # reversed flow: water climbs
):
climb(nr, nc, reached)
pacific: set = set()
atlantic: set = set()
for r in range(rows):
climb(r, 0, pacific) # left edge touches the Pacific
climb(r, cols - 1, atlantic) # right edge touches the Atlantic
for c in range(cols):
climb(0, c, pacific) # top edge: Pacific
climb(rows - 1, c, atlantic) # bottom edge: Atlantic
return [[r, c] for r, c in pacific & atlantic]
// LC 417. Reverse the flow: instead of simulating drainage from every cell,
// DFS INWARD from each ocean's border cells, moving only to equal-or-higher
// neighbors, and record each ocean's reachable set. The answer is the
// intersection -- cells marked by both sweeps.
vector<vector<int>> pacificAtlantic(vector<vector<int>> heights) {
int rows = static_cast<int>(heights.size()), cols = static_cast<int>(heights[0].size());
vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
auto climb = [&](auto&& self, vector<vector<bool>>& reach, int r, int c) -> void {
reach[r][c] = true;
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
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 && !reach[nr][nc] &&
heights[nr][nc] >= heights[r][c]) // reversed: only climb uphill or flat
self(self, reach, nr, nc);
}
};
for (int r = 0; r < rows; ++r) {
climb(climb, pacific, r, 0); // left edge: Pacific
climb(climb, atlantic, r, cols - 1); // right edge: Atlantic
}
for (int c = 0; c < cols; ++c) {
climb(climb, pacific, 0, c); // top edge: Pacific
climb(climb, atlantic, rows - 1, c); // bottom edge: Atlantic
}
vector<vector<int>> ans;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c)
if (pacific[r][c] && atlantic[r][c]) ans.push_back({r, c});
return ans;
}
/// LC 417. Reverse the flow: DFS inward from each ocean's border moving only
/// to equal-or-HIGHER neighbors, recording each ocean's reachable set. The
/// answer is the intersection, no per-cell simulation needed.
pub fn pacific_atlantic(heights: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
fn dfs(heights: &[Vec<i32>], reach: &mut Vec<Vec<bool>>, r: usize, c: usize) {
reach[r][c] = true;
for (nr, nc) in [(r.wrapping_sub(1), c), (r + 1, c), (r, c.wrapping_sub(1)), (r, c + 1)] {
if nr < heights.len()
&& nc < heights[0].len()
&& !reach[nr][nc]
&& heights[nr][nc] >= heights[r][c]
{
dfs(heights, reach, nr, nc);
}
}
}
let (rows, cols) = (heights.len(), heights[0].len());
let mut pacific = vec![vec![false; cols]; rows];
let mut atlantic = vec![vec![false; cols]; rows];
for r in 0..rows {
dfs(&heights, &mut pacific, r, 0);
dfs(&heights, &mut atlantic, r, cols - 1);
}
for c in 0..cols {
dfs(&heights, &mut pacific, 0, c);
dfs(&heights, &mut atlantic, rows - 1, c);
}
let mut ans = Vec::new();
for r in 0..rows {
for c in 0..cols {
if pacific[r][c] && atlantic[r][c] {
ans.push(vec![r as i32, c as i32]);
}
}
}
ans
}
/** LC 417. Reverse the flow: search inward from each ocean's border moving only to equal-or-HIGHER cells, then intersect the two reachable sets. */
export function pacificAtlantic(heights: number[][]): number[][] {
const rows = heights.length;
const cols = heights[0].length;
function reachable(seeds: [number, number][]): boolean[][] {
const seen: boolean[][] = Array.from({ length: rows }, () => new Array<boolean>(cols).fill(false));
function climb(r: number, c: number): void {
seen[r][c] = true;
for (const [dr, dc] of FOUR_DIRECTIONS) {
const nr = r + dr;
const nc = c + dc;
if (
nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
!seen[nr][nc] && heights[nr][nc] >= heights[r][c]
) {
climb(nr, nc);
}
}
}
for (const [r, c] of seeds) {
if (!seen[r][c]) climb(r, c);
}
return seen;
}
const pacificSeeds: [number, number][] = []; // top edge + left edge
const atlanticSeeds: [number, number][] = []; // bottom edge + right edge
for (let r = 0; r < rows; r++) {
pacificSeeds.push([r, 0]);
atlanticSeeds.push([r, cols - 1]);
}
for (let c = 0; c < cols; c++) {
pacificSeeds.push([0, c]);
atlanticSeeds.push([rows - 1, c]);
}
const pacific = reachable(pacificSeeds);
const atlantic = reachable(atlanticSeeds);
const ans: number[][] = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (pacific[r][c] && atlantic[r][c]) ans.push([r, c]);
}
}
return ans;
}
// LC 417. Reverse DFS inland from both coasts, climbing only uphill or flat;
// cells reached by BOTH sweeps drain to both oceans.
func pacificAtlantic(heights [][]int) [][]int {
rows, cols := len(heights), len(heights[0])
pacific := make([][]bool, rows)
atlantic := make([][]bool, rows)
for r := range pacific {
pacific[r] = make([]bool, cols)
atlantic[r] = make([]bool, cols)
}
var climb func(reach [][]bool, r, c int)
climb = func(reach [][]bool, r, c int) {
reach[r][c] = true
for _, d := range [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && !reach[nr][nc] &&
heights[nr][nc] >= heights[r][c] { // reversed flow: water climbs
climb(reach, nr, nc)
}
}
}
for r := 0; r < rows; r++ {
climb(pacific, r, 0) // left edge: Pacific
climb(atlantic, r, cols-1) // right edge: Atlantic
}
for c := 0; c < cols; c++ {
climb(pacific, 0, c) // top edge: Pacific
climb(atlantic, rows-1, c) // bottom edge: Atlantic
}
ans := [][]int{}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if pacific[r][c] && atlantic[r][c] {
ans = append(ans, []int{r, c})
}
}
}
return ans
}
// LC 417. Reverse the flow: DFS inland from each ocean's border moving only to
// equal-or-higher neighbors; cells reached by BOTH sweeps drain to both oceans.
func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
let rows = heights.count, cols = heights[0].count
var pacific = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
var atlantic = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
func climb(_ reach: inout [[Bool]], _ r: Int, _ c: Int) {
reach[r][c] = true
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
for d in 0..<4 {
let nr = r + dr[d], nc = c + dc[d]
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && !reach[nr][nc]
&& heights[nr][nc] >= heights[r][c] { // reversed: only climb uphill or flat
climb(&reach, nr, nc)
}
}
}
for r in 0..<rows {
climb(&pacific, r, 0) // left edge: Pacific
climb(&atlantic, r, cols - 1) // right edge: Atlantic
}
for c in 0..<cols {
climb(&pacific, 0, c) // top edge: Pacific
climb(&atlantic, rows - 1, c) // bottom edge: Atlantic
}
var ans: [[Int]] = []
for r in 0..<rows {
for c in 0..<cols where pacific[r][c] && atlantic[r][c] { ans.append([r, c]) }
}
return ans
}
10. Surrounded Regions
Medium · LC 130
Given a board of Xs and Os, flip every O region that is fully surrounded by Xs, leaving regions touching the border untouched. Run DFS or BFS from every border O, marking each reached O with a temporary letter, then sweep the board flipping unmarked Os to X and restoring marked ones. Inverting the question, finding the survivors instead of the captured regions, is the whole trick.
def solve_surrounded_regions(board: list[list[str]]) -> None:
"""LC 130. Surrounded Regions.
Invert the question: find the SURVIVORS instead of the captured.
DFS from every border 'O', marking each reached 'O' with a
temporary 'S', then sweep the board flipping unmarked 'O's to 'X'
and restoring the marked ones. Mutates the board; returns None.
O(mn) time, O(mn) stack in the worst case.
"""
rows, cols = len(board), len(board[0])
def mark_safe(r: int, c: int) -> None:
if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != "O":
return
board[r][c] = "S" # safe: connected to the border, must not be flipped
mark_safe(r + 1, c)
mark_safe(r - 1, c)
mark_safe(r, c + 1)
mark_safe(r, c - 1)
for r in range(rows):
mark_safe(r, 0)
mark_safe(r, cols - 1)
for c in range(cols):
mark_safe(0, c)
mark_safe(rows - 1, c)
for r in range(rows):
for c in range(cols):
# survivors revert to 'O'; every other cell (captured 'O' or
# original 'X') ends up 'X'
board[r][c] = "O" if board[r][c] == "S" else "X"
// LC 130. Invert the question: find the SURVIVORS instead of the captured.
// DFS from every border O, relabeling each reached O with a temporary 'T';
// then one sweep flips the unmarked Os to X (truly surrounded) and restores
// the marked ones. The board is modified in place.
void solveSurroundedRegions(vector<vector<char>>& board) {
int rows = static_cast<int>(board.size()), cols = static_cast<int>(board[0].size());
auto mark = [&](auto&& self, int r, int c) -> void {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O') return;
board[r][c] = 'T'; // temporary letter = "connected to the border"
self(self, r + 1, c);
self(self, r - 1, c);
self(self, r, c + 1);
self(self, r, c - 1);
};
for (int r = 0; r < rows; ++r) {
mark(mark, r, 0);
mark(mark, r, cols - 1);
}
for (int c = 0; c < cols; ++c) {
mark(mark, 0, c);
mark(mark, rows - 1, c);
}
for (auto& row : board)
for (char& cell : row) cell = (cell == 'T') ? 'O' : 'X'; // restore / capture
}
/// LC 130. Invert the question: find the survivors, not the captured. Mark
/// every border-connected 'O' with a temporary 'T', then sweep, flipping
/// unmarked 'O' to 'X' and restoring 'T' to 'O'.
pub fn solve_surrounded_regions(board: &mut Vec<Vec<char>>) {
fn mark(board: &mut Vec<Vec<char>>, r: usize, c: usize) {
if r >= board.len() || c >= board[0].len() || board[r][c] != 'O' {
return;
}
board[r][c] = 'T';
mark(board, r + 1, c);
mark(board, r.wrapping_sub(1), c);
mark(board, r, c + 1);
mark(board, r, c.wrapping_sub(1));
}
let (rows, cols) = (board.len(), board[0].len());
for r in 0..rows {
mark(board, r, 0);
mark(board, r, cols - 1);
}
for c in 0..cols {
mark(board, 0, c);
mark(board, rows - 1, c);
}
for row in board.iter_mut() {
for cell in row.iter_mut() {
*cell = if *cell == 'T' { 'O' } else { 'X' };
}
}
}
/** LC 130. Invert the question: flood from every border 'O' marking survivors 'S', then flip unmarked 'O's to 'X' and restore the marks. */
export function solveSurroundedRegions(board: string[][]): void {
const rows = board.length;
const cols = board[0].length;
function save(r: number, c: number): void {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== "O") return;
board[r][c] = "S"; // survivor: connected to the border
save(r + 1, c);
save(r - 1, c);
save(r, c + 1);
save(r, c - 1);
}
for (let r = 0; r < rows; r++) {
save(r, 0);
save(r, cols - 1);
}
for (let c = 0; c < cols; c++) {
save(0, c);
save(rows - 1, c);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === "O") board[r][c] = "X"; // captured
else if (board[r][c] === "S") board[r][c] = "O"; // restored
}
}
}
// LC 130. Border DFS finds the SURVIVORS: mark every 'O' reachable from the
// edge with a temporary 'T', then flip unmarked 'O's to 'X' and restore the rest.
func solveSurroundedRegions(board [][]byte) {
rows, cols := len(board), len(board[0])
var mark func(r, c int)
mark = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O' {
return
}
board[r][c] = 'T' // temporary letter = "connected to the border"
mark(r+1, c)
mark(r-1, c)
mark(r, c+1)
mark(r, c-1)
}
for r := 0; r < rows; r++ {
mark(r, 0)
mark(r, cols-1)
}
for c := 0; c < cols; c++ {
mark(0, c)
mark(rows-1, c)
}
for r := range board {
for c := range board[r] {
if board[r][c] == 'T' {
board[r][c] = 'O' // survivor: restore
} else {
board[r][c] = 'X' // captured 'O' or original 'X'
}
}
}
}
// LC 130. Invert the question: DFS from every border 'O' marks the SURVIVORS
// with 'T'; one sweep then captures unmarked 'O's and restores the marked.
func solveSurroundedRegions(_ board: inout [[Character]]) {
let rows = board.count, cols = board[0].count
func mark(_ r: Int, _ c: Int) {
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != "O" { return }
board[r][c] = "T" // temporary letter = "connected to the border"
mark(r + 1, c)
mark(r - 1, c)
mark(r, c + 1)
mark(r, c - 1)
}
for r in 0..<rows {
mark(r, 0)
mark(r, cols - 1)
}
for c in 0..<cols {
mark(0, c)
mark(rows - 1, c)
}
for r in 0..<rows {
for c in 0..<cols {
board[r][c] = board[r][c] == "T" ? "O" : "X" // restore / capture
}
}
}
11. Open The Lock
Medium · LC 752
Given deadend combinations and a target, return the fewest single-wheel turns taking a four-wheel lock from 0000 to the target. BFS over the implicit graph whose nodes are the 10000 wheel states and whose edges are the eight one-turn moves, each wheel stepping up or down with wraparound. Treat deadends as already visited before starting, and check 0000 itself: if it is a deadend, return -1 immediately.
def open_lock(deadends: list[str], target: str) -> int:
"""LC 752. Open the Lock.
BFS over the implicit graph of the 10000 wheel states; each state
has eight neighbors (four wheels, each turned up or down with
wraparound). Seeding visited with the deadends turns them into
walls the search flows around -- but check "0000" itself first.
O(10^4 * 8) time, O(10^4) space.
"""
visited = set(deadends)
if "0000" in visited:
return -1 # the start itself is a deadend: the lock can never move
queue = deque([("0000", 0)])
visited.add("0000")
while queue:
state, turns = queue.popleft()
if state == target:
return turns
for i in range(4):
digit = int(state[i])
for spin in (1, -1):
neighbor = state[:i] + str((digit + spin) % 10) + state[i + 1:]
if neighbor not in visited:
visited.add(neighbor) # mark on enqueue, never on dequeue
queue.append((neighbor, turns + 1))
return -1
// LC 752. BFS over the implicit graph of the 10000 wheel states; each state
// has eight neighbors (four wheels, +1 or -1 with wraparound, -1 done as +9
// mod 10). Mark every deadend visited BEFORE starting so the search simply
// routes around them -- and if 0000 itself is a deadend, return -1 at once.
int openLock(vector<string> deadends, string target) {
vector<bool> seen(10000, false);
for (const string& d : deadends) seen[stoi(d)] = true;
if (seen[0]) return -1; // the lock is stuck before the first turn
queue<pair<string, int>> q;
q.push({"0000", 0});
seen[0] = true;
while (!q.empty()) {
auto [state, turns] = q.front();
q.pop();
if (state == target) return turns;
for (int wheel = 0; wheel < 4; ++wheel)
for (int step : {1, 9}) { // +1 and -1 with wraparound
string next = state;
next[wheel] = static_cast<char>('0' + (next[wheel] - '0' + step) % 10);
int idx = stoi(next);
if (!seen[idx]) {
seen[idx] = true;
q.push({next, turns + 1});
}
}
}
return -1;
}
/// LC 752. BFS over the implicit graph of 10000 wheel states as [u8; 4],
/// eight one-turn moves per state (each wheel +-1 with wraparound). Deadends
/// are seeded as already visited; if "0000" itself is a deadend, return -1.
pub fn open_lock(deadends: Vec<String>, target: String) -> i32 {
fn key(s: &str) -> [u8; 4] {
let b = s.as_bytes();
[b[0], b[1], b[2], b[3]]
}
let mut visited: HashSet<[u8; 4]> = deadends.iter().map(|s| key(s)).collect();
let start = [b'0'; 4];
let target = key(&target);
if visited.contains(&start) {
return -1;
}
if start == target {
return 0;
}
visited.insert(start);
let mut queue = VecDeque::from([(start, 0)]);
while let Some((state, turns)) = queue.pop_front() {
for i in 0..4 {
for delta in [1u8, 9] {
// +1 and -1 are the same move mod 10
let mut next = state;
next[i] = b'0' + (state[i] - b'0' + delta) % 10;
if next == target {
return turns + 1;
}
if visited.insert(next) {
queue.push_back((next, turns + 1));
}
}
}
}
-1
}
/** LC 752. BFS over the 10000 wheel states with eight one-turn edges; pre-seed deadends as visited and bail early if "0000" itself is dead. */
export function openLock(deadends: string[], target: string): number {
const visited = new Set(deadends);
if (visited.has("0000")) return -1;
if (target === "0000") return 0;
visited.add("0000");
const queue: [string, number][] = [["0000", 0]];
let head = 0;
while (head < queue.length) {
const [state, turns] = queue[head++];
for (let i = 0; i < 4; i++) {
const digit = state.charCodeAt(i) - 48;
for (const delta of [1, 9]) {
// +1 and -1 with wraparound (adding 9 mod 10 turns the wheel back)
const next = state.slice(0, i) + String((digit + delta) % 10) + state.slice(i + 1);
if (next === target) return turns + 1;
if (!visited.has(next)) {
visited.add(next);
queue.push([next, turns + 1]);
}
}
}
}
return -1;
}
// LC 752. BFS over the 10000 wheel states, eight neighbors each (four wheels,
// +1/-1 with wraparound); deadends are pre-marked visited so the search routes around them.
func openLock(deadends []string, target string) int {
toIdx := func(s string) int {
return int(s[0]-'0')*1000 + int(s[1]-'0')*100 + int(s[2]-'0')*10 + int(s[3]-'0')
}
seen := make([]bool, 10000)
for _, d := range deadends {
seen[toIdx(d)] = true
}
if seen[0] {
return -1 // the lock is stuck before the first turn
}
type entry struct {
state string
turns int
}
queue := []entry{{"0000", 0}}
seen[0] = true
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
if cur.state == target {
return cur.turns
}
for wheel := 0; wheel < 4; wheel++ {
for _, step := range [2]int{1, 9} { // +1 and -1 with wraparound
next := []byte(cur.state)
next[wheel] = byte('0' + (int(next[wheel]-'0')+step)%10)
idx := toIdx(string(next))
if !seen[idx] {
seen[idx] = true // mark on enqueue, never on dequeue
queue = append(queue, entry{string(next), cur.turns + 1})
}
}
}
}
return -1
}
// LC 752. BFS over the 10000 wheel states, eight neighbors each (four wheels,
// +1 or -1 with wraparound); deadends are pre-marked visited so the search
// flows around them -- but a deadend start means the lock never moves.
func openLock(_ deadends: [String], _ target: String) -> Int {
var seen = [Bool](repeating: false, count: 10000)
for d in deadends { seen[Int(d)!] = true }
if seen[0] { return -1 } // the lock is stuck before the first turn
let goal = Int(target)!
var queue: [(Int, Int)] = [(0, 0)] // (state, turns)
var head = 0
seen[0] = true
let place = [1000, 100, 10, 1]
while head < queue.count {
let (state, turns) = queue[head]
head += 1
if state == goal { return turns }
for p in place {
let digit = (state / p) % 10
for step in [1, 9] { // +1 and -1 with wraparound
let next = state - digit * p + ((digit + step) % 10) * p
if !seen[next] {
seen[next] = true // mark on enqueue, never on dequeue
queue.append((next, turns + 1))
}
}
}
}
return -1
}
12. Course Schedule
Medium · LC 207
Given numCourses and prerequisite pairs, decide whether every course can be finished, which means the directed prerequisite graph has no cycle. Run DFS with three states, unvisited, in progress, and done, flagging a cycle when an in-progress node is re-entered, or use Kahn's algorithm and check that every node gets processed. The in-progress state is essential; a plain visited set cannot tell a cycle from a diamond reconvergence.
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
}
13. Course Schedule II
Medium · LC 210
Given numCourses and prerequisite pairs, return any valid order to take all courses, or an empty array if a cycle makes it impossible. Either run Kahn's algorithm, repeatedly dequeuing zero-indegree nodes and decrementing their neighbors, or DFS with cycle detection and reverse the postorder. Remember that a node finishes DFS only after everything it points to, which is exactly why reversed postorder is a valid topological order.
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 : []
}
14. Graph Valid Tree
Medium · LC 261
Given n nodes and an undirected edge list, decide whether they form a valid tree, meaning connected and free of cycles. Check that the edge count is exactly n-1, then confirm connectivity with one DFS or BFS, or use union-find where every merge must join two different roots. With exactly n-1 edges, connected implies acyclic, so the count does half the work and only one property needs checking.
def valid_tree(n: int, edges: list[list[int]]) -> bool:
"""LC 261. Graph Valid Tree.
A tree is connected and acyclic, but with exactly n-1 edges each
property implies the other -- so check the edge count, then confirm
connectivity with a single DFS. Fewer edges means disconnected,
more means a cycle, n-1 and connected means tree. O(V + E) time
and space.
"""
if len(edges) != n - 1:
return False # wrong count: guaranteed cycle or disconnection
graph: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
seen = {0}
stack = [0]
while stack:
node = stack.pop()
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return len(seen) == n # n-1 edges + connected => acyclic comes for free
// LC 261. A tree is exactly "n-1 edges + connected", and with the edge count
// pinned at n-1, connected already implies acyclic -- so the count check does
// half the work and one DFS from node 0 confirming all n nodes are reachable
// finishes the proof. (Union-find with every merge joining two distinct
// roots works equally well.)
bool validTree(int n, vector<vector<int>> edges) {
if (static_cast<int>(edges.size()) != n - 1) return false; // count does half the work
vector<vector<int>> graph(n);
for (const auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
vector<bool> seen(n, false);
int reached = 0;
auto dfs = [&](auto&& self, int node) -> void {
seen[node] = true;
++reached;
for (int next : graph[node])
if (!seen[next]) self(self, next);
};
dfs(dfs, 0);
return reached == n;
}
/// LC 261. Exactly n - 1 edges plus connected implies acyclic, so the edge
/// count does half the work: check the count, then one DFS from node 0 must
/// reach all n nodes.
pub fn valid_tree(n: i32, edges: Vec<Vec<i32>>) -> bool {
let n = n as usize;
if edges.len() != n - 1 {
return false;
}
let mut graph = vec![Vec::new(); n];
for e in &edges {
graph[e[0] as usize].push(e[1] as usize);
graph[e[1] as usize].push(e[0] as usize);
}
let mut seen = vec![false; n];
seen[0] = true;
let mut reached = 1;
let mut stack = vec![0usize];
while let Some(u) = stack.pop() {
for &v in &graph[u] {
if !seen[v] {
seen[v] = true;
reached += 1;
stack.push(v);
}
}
}
reached == n
}
/** LC 261. Exactly n-1 edges plus connected implies acyclic, so the count check does half the work and one BFS finishes the proof. */
export function validTree(n: number, edges: number[][]): boolean {
if (edges.length !== n - 1) return false;
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
const seen = new Array<boolean>(n).fill(false);
seen[0] = true;
const queue: number[] = [0];
let head = 0;
let reached = 1;
while (head < queue.length) {
const node = queue[head++];
for (const next of graph[node]) {
if (!seen[next]) {
seen[next] = true;
reached++;
queue.push(next);
}
}
}
return reached === n;
}
// LC 261. Exactly n-1 edges plus connected (one DFS from node 0) makes a tree;
// with the count pinned, acyclic comes for free.
func validTree(n int, edges [][]int) bool {
if len(edges) != n-1 {
return false // wrong count: guaranteed cycle or disconnection
}
graph := make([][]int, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
graph[e[1]] = append(graph[e[1]], e[0])
}
seen := make([]bool, n)
reached := 0
var dfs func(node int)
dfs = func(node int) {
seen[node] = true
reached++
for _, next := range graph[node] {
if !seen[next] {
dfs(next)
}
}
}
dfs(0)
return reached == n
}
// LC 261. A tree is exactly "n-1 edges + connected", and with the count pinned
// at n-1, connected already implies acyclic -- so one DFS finishes the proof.
func validTree(_ n: Int, _ edges: [[Int]]) -> Bool {
if edges.count != n - 1 { return false } // wrong count: cycle or disconnection
var graph = [[Int]](repeating: [], count: n)
for e in edges {
graph[e[0]].append(e[1])
graph[e[1]].append(e[0])
}
var seen = [Bool](repeating: false, count: n)
var reached = 0
func dfs(_ node: Int) {
seen[node] = true
reached += 1
for next in graph[node] where !seen[next] { dfs(next) }
}
dfs(0)
return reached == n // n-1 edges + connected => acyclic comes for free
}
15. Course Schedule IV
Medium · LC 1462
Given prerequisite edges between courses and queries asking whether u is a prerequisite of v, answer each query including indirect chains. Process nodes in topological order, propagating to each node the full set of its ancestors, namely each direct prerequisite plus that prerequisite's own ancestor set. Precomputing full reachability is the point, since queries become O(1) set lookups; Floyd-Warshall over a boolean matrix achieves the same in O(n^3).
def check_if_prerequisite(
num_courses: int, prerequisites: list[list[int]], queries: list[list[int]]
// LC 1462. Precompute FULL reachability so each query becomes an O(1)
// lookup: process courses in topological order (Kahn), and when relaxing an
// edge u -> v, fold u plus u's entire ancestor set into v's. By the time u
// is dequeued its ancestor row is complete, so the propagation is sound.
// Row v of the boolean matrix ends up holding every direct and indirect
// prerequisite of v (std::bitset rows would pack this 64x tighter).
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> prerequisites,
vector<vector<int>> queries) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (const auto& p : prerequisites) {
graph[p[0]].push_back(p[1]);
++indegree[p[1]];
}
vector<vector<bool>> ancestor(numCourses, vector<bool>(numCourses, false));
queue<int> q;
for (int node = 0; node < numCourses; ++node)
if (indegree[node] == 0) q.push(node);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int next : graph[node]) {
ancestor[next][node] = true; // direct prerequisite
for (int a = 0; a < numCourses; ++a)
if (ancestor[node][a]) ancestor[next][a] = true; // plus its ancestors
if (--indegree[next] == 0) q.push(next);
}
}
vector<bool> ans;
for (const auto& query : queries) ans.push_back(ancestor[query[1]][query[0]]);
return ans;
}
/// LC 1462. Precompute full reachability so each query is an O(1) lookup:
/// process nodes in Kahn topological order, propagating to each node its
/// direct prerequisites plus their entire ancestor sets.
pub fn check_if_prerequisite(
num_courses: i32,
prerequisites: Vec<Vec<i32>>,
queries: Vec<Vec<i32>>,
) -> Vec<bool> {
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[0] as usize].push(p[1] as usize);
indegree[p[1] as usize] += 1;
}
let mut ancestors: Vec<HashSet<usize>> = vec![HashSet::new(); n];
let mut queue: VecDeque<usize> = (0..n).filter(|&node| indegree[node] == 0).collect();
while let Some(u) = queue.pop_front() {
let anc_u = ancestors[u].clone();
for &v in &graph[u] {
ancestors[v].insert(u);
ancestors[v].extend(anc_u.iter().copied());
indegree[v] -= 1;
if indegree[v] == 0 {
queue.push_back(v);
}
}
}
queries.iter().map(|q| ancestors[q[1] as usize].contains(&(q[0] as usize))).collect()
}
/** LC 1462. Kahn topological order propagating full ancestor sets (direct prereq + its ancestors), so each query is an O(1) set lookup. */
export function checkIfPrerequisite(
numCourses: number,
prerequisites: number[][],
queries: number[][],
): boolean[] {
const graph: number[][] = Array.from({ length: numCourses }, () => []);
const indegree = new Array<number>(numCourses).fill(0);
for (const [pre, course] of prerequisites) {
graph[pre].push(course);
indegree[course]++;
}
const ancestors: Set<number>[] = Array.from({ length: numCourses }, () => new Set<number>());
const queue: number[] = [];
for (let node = 0; node < numCourses; node++) {
if (indegree[node] === 0) queue.push(node);
}
let head = 0;
while (head < queue.length) {
const node = queue[head++];
for (const next of graph[node]) {
ancestors[next].add(node); // the direct prerequisite...
for (const anc of ancestors[node]) ancestors[next].add(anc); // ...plus everything before it
if (--indegree[next] === 0) queue.push(next);
}
}
return queries.map(([u, v]) => ancestors[v].has(u));
}
// LC 1462. Kahn's topological order propagates FULL ancestor sets edge by
// edge, so each query becomes an O(1) lookup in a boolean matrix.
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, p := range prerequisites {
graph[p[0]] = append(graph[p[0]], p[1])
indegree[p[1]]++
}
ancestor := make([][]bool, numCourses)
for i := range ancestor {
ancestor[i] = make([]bool, numCourses)
}
queue := []int{}
for node := 0; node < numCourses; node++ {
if indegree[node] == 0 {
queue = append(queue, node)
}
}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, next := range graph[node] {
ancestor[next][node] = true // direct prerequisite
for a := 0; a < numCourses; a++ {
if ancestor[node][a] {
ancestor[next][a] = true // plus everything before it
}
}
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
ans := make([]bool, len(queries))
for i, q := range queries {
ans[i] = ancestor[q[1]][q[0]]
}
return ans
}
// LC 1462. Kahn's topological order propagates ancestor sets: fold each course
// plus its full ancestor row into every successor, making queries O(1) lookups.
func checkIfPrerequisite(_ numCourses: Int, _ prerequisites: [[Int]], _ queries: [[Int]]) -> [Bool] {
var graph = [[Int]](repeating: [], count: numCourses)
var indegree = [Int](repeating: 0, count: numCourses)
for p in prerequisites {
graph[p[0]].append(p[1])
indegree[p[1]] += 1
}
var ancestor = [[Bool]](repeating: [Bool](repeating: false, count: numCourses), count: numCourses)
var queue: [Int] = []
for node in 0..<numCourses where indegree[node] == 0 { queue.append(node) }
var head = 0
while head < queue.count {
let node = queue[head]
head += 1
for next in graph[node] {
ancestor[next][node] = true // direct prerequisite
for a in 0..<numCourses where ancestor[node][a] { ancestor[next][a] = true } // plus its ancestors
indegree[next] -= 1
if indegree[next] == 0 { queue.append(next) }
}
}
return queries.map { ancestor[$0[1]][$0[0]] }
}
16. Number of Connected Components In An Undirected Graph
Medium · LC 323
Given n nodes labeled 0 to n-1 and an undirected edge list, return the number of connected components. Start a counter at n and run union-find over the edges, decrementing once for each union that actually merges two distinct roots. Counting successful merges is the trick, since each one reduces the component count by exactly one; DFS launches from unvisited nodes work just as well.
def count_components(n: int, edges: list[list[int]]) -> int:
"""LC 323. Number of Connected Components in an Undirected Graph.
Union-find: start the count at n and decrement once per union that
actually merges two distinct roots, since each real merge removes
exactly one component. Path compression repoints every node on the
walked chain straight at its root; union by size hangs the smaller
tree under the larger so chains stay short. Together they make
each operation effectively O(1) (inverse Ackermann). O(n + E) time,
O(n) space.
"""
parent = list(range(n))
size = [1] * n
components = n
def find(node: int) -> int:
root = node
while parent[root] != root:
root = parent[root]
# path compression: repoint everything on the walked chain at the
# root so the next find on any of these nodes is one hop
while parent[node] != root:
parent[node], node = root, parent[node]
return root
def union(a: int, b: int) -> bool:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return False # already one component: nothing merged
# union by size: the smaller tree hangs under the larger, so no
# node's depth grows unless its tree at least doubles
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
size[root_a] += size[root_b]
return True
for a, b in edges:
if union(a, b):
components -= 1 # only successful merges shrink the count
return components
// LC 323. Union-find with path compression and union by size: start the
// count at n and decrement once per union that actually merges two distinct
// roots, since exactly those merges reduce the component count by one.
int countComponents(int n, vector<vector<int>> edges) {
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
vector<int> size(n, 1);
auto find = [&](auto&& self, int x) -> int {
if (parent[x] != x) parent[x] = self(self, parent[x]); // path compression
return parent[x];
};
int components = n;
for (const auto& e : edges) {
int a = find(find, e[0]), b = find(find, e[1]);
if (a == b) continue; // already connected: no merge, no decrement
if (size[a] < size[b]) swap(a, b); // union by size: small tree under large
parent[b] = a;
size[a] += size[b];
--components;
}
return components;
}
/// LC 323. Union-find with path compression (halving) + union by size:
/// start the counter at n and decrement once per union that actually merges
/// two distinct roots -- each successful merge removes exactly one component.
pub fn count_components(n: i32, edges: Vec<Vec<i32>>) -> i32 {
fn find(parent: &mut [usize], mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
x
}
let n = n as usize;
let mut parent: Vec<usize> = (0..n).collect();
let mut size = vec![1usize; n];
let mut count = n as i32;
for e in &edges {
let (mut ra, mut rb) = (find(&mut parent, e[0] as usize), find(&mut parent, e[1] as usize));
if ra == rb {
continue;
}
if size[ra] < size[rb] {
std::mem::swap(&mut ra, &mut rb);
}
parent[rb] = ra; // smaller tree hangs under the bigger root
size[ra] += size[rb];
count -= 1;
}
count
}
/** LC 323. Union-find with path compression + union by size; start at n and decrement once per merge of two DISTINCT roots. */
export function countComponents(n: number, edges: number[][]): number {
const parent = Array.from({ length: n }, (_, i) => i);
const size = new Array<number>(n).fill(1);
function find(x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path compression by halving
x = parent[x];
}
return x;
}
let components = n;
for (const [a, b] of edges) {
let ra = find(a);
let rb = find(b);
if (ra === rb) continue; // already one component; no merge, no decrement
if (size[ra] < size[rb]) [ra, rb] = [rb, ra]; // union by size: small root under big
parent[rb] = ra;
size[ra] += size[rb];
components--;
}
return components;
}
// LC 323. Union-find with path compression and union by size: start the count
// at n and decrement once per union that actually merges two distinct roots.
func countComponents(n int, edges [][]int) int {
parent := make([]int, n)
size := make([]int, n)
for i := range parent {
parent[i] = i
size[i] = 1
}
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x]) // path compression
}
return parent[x]
}
components := n
for _, e := range edges {
a, b := find(e[0]), find(e[1])
if a == b {
continue // already connected: no merge, no decrement
}
if size[a] < size[b] {
a, b = b, a // union by size: small tree under large
}
parent[b] = a
size[a] += size[b]
components--
}
return components
}
// LC 323. Union-find with path halving and union by size: start the count at n
// and decrement once per union that actually merges two distinct roots.
func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
var parent = Array(0..<n)
var size = [Int](repeating: 1, count: n)
func find(_ x: Int) -> Int {
var x = x
while parent[x] != x {
parent[x] = parent[parent[x]] // path halving compresses as we walk
x = parent[x]
}
return x
}
var components = n
for e in edges {
var a = find(e[0]), b = find(e[1])
if a == b { continue } // already connected: no merge, no decrement
if size[a] < size[b] { swap(&a, &b) } // union by size: small tree under large
parent[b] = a
size[a] += size[b]
components -= 1
}
return components
}
17. Redundant Connection
Medium · LC 684
Given a graph built by adding one extra edge to a tree of n nodes, return the edge whose removal restores a tree, preferring the one appearing last in the input. Run union-find over the edges in order, and the first edge whose two endpoints already share a root is the answer. That edge closes the unique cycle, and processing in input order automatically satisfies the last-edge tiebreak.
def find_redundant_connection(edges: list[list[int]]) -> list[int]:
"""LC 684. Redundant Connection.
The graph is a tree plus ONE extra edge. Union the edges in input
order; the first edge whose endpoints already share a root closes
the unique cycle and is the answer -- processing in input order
automatically satisfies the "last in input" tiebreak.
O(E) time (with compression), O(n) space.
"""
parent = list(range(len(edges) + 1)) # a tree of n nodes has n edges here; 1-indexed
def find(node: int) -> int:
while parent[node] != node:
parent[node] = parent[parent[node]] # path halving compresses as we walk
node = parent[node]
return node
for a, b in edges:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return [a, b] # endpoints already joined: this edge closes the cycle
parent[root_b] = root_a
return [] # unreachable on valid input
// LC 684. Union-find over the edges IN INPUT ORDER: the first edge whose two
// endpoints already share a root closes the unique cycle and is the answer.
// Processing in order automatically satisfies the prefer-the-last tiebreak,
// because every earlier cycle edge unioned successfully.
vector<int> findRedundantConnection(vector<vector<int>> edges) {
int n = static_cast<int>(edges.size()); // n nodes labeled 1..n, n edges
vector<int> parent(n + 1);
iota(parent.begin(), parent.end(), 0);
vector<int> size(n + 1, 1);
auto find = [&](auto&& self, int x) -> int {
if (parent[x] != x) parent[x] = self(self, parent[x]);
return parent[x];
};
for (const auto& e : edges) {
int a = find(find, e[0]), b = find(find, e[1]);
if (a == b) return e; // endpoints already connected: this edge closes the cycle
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
}
return {};
}
/// LC 684. Union-find over the edges in input order: the first edge whose
/// endpoints already share a root closes the unique cycle, and input order
/// automatically satisfies the return-the-last-edge tiebreak.
pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
fn find(parent: &mut [usize], mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]];
x = parent[x];
}
x
}
let n = edges.len();
let mut parent: Vec<usize> = (0..=n).collect(); // nodes are 1..=n
let mut size = vec![1usize; n + 1];
for e in &edges {
let (mut ra, mut rb) = (find(&mut parent, e[0] as usize), find(&mut parent, e[1] as usize));
if ra == rb {
return e.clone();
}
if size[ra] < size[rb] {
std::mem::swap(&mut ra, &mut rb);
}
parent[rb] = ra;
size[ra] += size[rb];
}
Vec::new()
}
/** LC 684. Union edges in input order; the first edge whose endpoints already share a root closes the unique cycle, and input order satisfies the last-edge tiebreak. */
export function findRedundantConnection(edges: number[][]): number[] {
const n = edges.length; // n edges over n nodes labeled 1..n
const parent = Array.from({ length: n + 1 }, (_, i) => i);
function find(x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
for (const edge of edges) {
const ra = find(edge[0]);
const rb = find(edge[1]);
if (ra === rb) return edge;
parent[ra] = rb;
}
return [];
}
// LC 684. Union the edges in INPUT order; the first edge whose endpoints
// already share a root closes the unique cycle and is the answer.
func findRedundantConnection(edges [][]int) []int {
n := len(edges) // n nodes labeled 1..n, n edges
parent := make([]int, n+1)
size := make([]int, n+1)
for i := range parent {
parent[i] = i
size[i] = 1
}
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x]) // path compression
}
return parent[x]
}
for _, e := range edges {
a, b := find(e[0]), find(e[1])
if a == b {
return e // endpoints already connected: this edge closes the cycle
}
if size[a] < size[b] {
a, b = b, a
}
parent[b] = a
size[a] += size[b]
}
return nil // unreachable on valid input
}
// LC 684. Union the edges IN INPUT ORDER: the first edge whose endpoints
// already share a root closes the unique cycle and is the answer.
func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
let n = edges.count // n nodes labeled 1..n, n edges
var parent = Array(0...n)
var size = [Int](repeating: 1, count: n + 1)
func find(_ x: Int) -> Int {
var x = x
while parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
for e in edges {
var a = find(e[0]), b = find(e[1])
if a == b { return e } // endpoints already joined: this edge closes the cycle
if size[a] < size[b] { swap(&a, &b) }
parent[b] = a
size[a] += size[b]
}
return [] // unreachable on valid input
}
18. Accounts Merge
Medium · LC 721
Given accounts as a name followed by a list of emails, merge accounts sharing any email and return each merged account with its emails sorted. Run union-find over the emails, unioning all emails within each account, then group every email under its root representative. Accounts sharing an email are guaranteed to share a name, so the name rides along; remember to sort each group's emails before output.
def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
"""LC 721. Accounts Merge.
Union-find over EMAILS: within each account, union every email with
the account's first email, so accounts sharing any email collapse
into one set. Then group emails by root, sort each group, and
prepend the name -- accounts sharing an email are guaranteed to
share a name, so any member's name works. O(total emails) unions
plus O(E log E) for the sorts.
"""
parent: dict = {} # email -> parent email
owner_name: dict = {} # email -> account holder's name, for output
def find(email: str) -> str:
root = email
while parent[root] != root:
root = parent[root]
while parent[email] != root: # path compression
parent[email], email = root, parent[email]
return root
for account in accounts:
name, emails = account[0], account[1:]
for email in emails:
parent.setdefault(email, email)
owner_name[email] = name
# tie every email to the account's FIRST email; transitivity
# across accounts comes from shared emails sharing a root
root_first, root_this = find(emails[0]), find(email)
if root_first != root_this:
parent[root_this] = root_first
grouped: dict = {} # root email -> all emails in its set
for email in parent:
grouped.setdefault(find(email), []).append(email)
return [[owner_name[root]] + sorted(group) for root, group in grouped.items()]
// LC 721. Union-find over EMAILS, not accounts: give each email an index on
// first sight, union every email in an account with that account's first
// email, then bucket all emails under their final root. Accounts sharing an
// email are guaranteed to share a name, so the root's name rides along; each
// group's emails are sorted before output (account order is unspecified).
vector<vector<string>> accountsMerge(vector<vector<string>> accounts) {
unordered_map<string, int> id; // email -> union-find index
vector<string> emailOf; // index -> email
vector<int> owner; // index -> account that names this email
vector<int> parent, size;
auto find = [&](auto&& self, int x) -> int {
if (parent[x] != x) parent[x] = self(self, parent[x]);
return parent[x];
};
auto unite = [&](int a, int b) -> void {
a = find(find, a);
b = find(find, b);
if (a == b) return;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
};
for (int acct = 0; acct < static_cast<int>(accounts.size()); ++acct)
for (size_t i = 1; i < accounts[acct].size(); ++i) {
const string& email = accounts[acct][i];
if (!id.count(email)) {
id[email] = static_cast<int>(emailOf.size());
emailOf.push_back(email);
owner.push_back(acct);
parent.push_back(static_cast<int>(parent.size()));
size.push_back(1);
}
if (i > 1) unite(id[accounts[acct][1]], id[email]); // chain to first email
}
unordered_map<int, vector<string>> groups; // root index -> its emails
for (int e = 0; e < static_cast<int>(emailOf.size()); ++e)
groups[find(find, e)].push_back(emailOf[e]);
vector<vector<string>> ans;
for (auto& [root, emails] : groups) {
sort(emails.begin(), emails.end());
vector<string> account{accounts[owner[root]][0]}; // shared name rides along
account.insert(account.end(), emails.begin(), emails.end());
ans.push_back(move(account));
}
return ans;
}
/// LC 721. Union-find over the EMAILS, not the accounts: union all emails
/// within each account, then group every email under its root. Accounts
/// sharing an email are guaranteed to share a name, so the name rides along;
/// each group's emails are sorted before output.
pub fn accounts_merge(accounts: Vec<Vec<String>>) -> Vec<Vec<String>> {
fn find(parent: &mut [usize], mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]];
x = parent[x];
}
x
}
let mut email_id: HashMap<&str, usize> = HashMap::new();
let mut id_account: Vec<usize> = Vec::new(); // email id -> owning account (for the name)
for (account, row) in accounts.iter().enumerate() {
for email in &row[1..] {
email_id.entry(email).or_insert_with(|| {
id_account.push(account);
id_account.len() - 1
});
}
}
let mut parent: Vec<usize> = (0..id_account.len()).collect();
let mut size = vec![1usize; id_account.len()];
for row in &accounts {
let first = email_id[row[1].as_str()];
for email in &row[2..] {
let (mut ra, mut rb) =
(find(&mut parent, first), find(&mut parent, email_id[email.as_str()]));
if ra == rb {
continue;
}
if size[ra] < size[rb] {
std::mem::swap(&mut ra, &mut rb);
}
parent[rb] = ra;
size[ra] += size[rb];
}
}
let mut groups: HashMap<usize, Vec<&str>> = HashMap::new();
for (&email, &id) in &email_id {
groups.entry(find(&mut parent, id)).or_default().push(email);
}
let mut ans = Vec::new();
for (root, mut emails) in groups {
emails.sort_unstable();
let mut row = Vec::with_capacity(emails.len() + 1);
row.push(accounts[id_account[root]][0].clone());
row.extend(emails.into_iter().map(str::to_string));
ans.push(row);
}
ans
}
/** LC 721. Union-find over EMAILS, anchoring each account's emails to its first; then group by root (the name rides along) and sort each group. */
export function accountsMerge(accounts: string[][]): string[][] {
const parent = new Map<string, string>();
const owner = new Map<string, string>(); // email -> account name
function find(email: string): string {
let root = email;
while (parent.get(root) !== root) root = parent.get(root)!;
while (parent.get(email) !== root) {
// path compression: point every node on the walk straight at the root
const next = parent.get(email)!;
parent.set(email, root);
email = next;
}
return root;
}
for (const [name, ...emails] of accounts) {
for (const email of emails) {
if (!parent.has(email)) {
parent.set(email, email);
owner.set(email, name);
}
const ra = find(emails[0]);
const rb = find(email);
if (ra !== rb) parent.set(rb, ra);
}
}
const groups = new Map<string, string[]>();
for (const email of parent.keys()) {
const root = find(email);
let group = groups.get(root);
if (!group) {
group = [];
groups.set(root, group);
}
group.push(email);
}
const ans: string[][] = [];
for (const [root, emails] of groups) {
ans.push([owner.get(root)!, ...emails.sort()]);
}
return ans;
}
// LC 721. Union-find over EMAILS: chain every email in an account to the
// account's first email, then bucket by root, sort, and prepend the name.
func accountsMerge(accounts [][]string) [][]string {
id := map[string]int{} // email -> union-find index
emailOf := []string{} // index -> email
owner := []int{} // index -> account that names this email
parent := []int{}
size := []int{}
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x]) // path compression
}
return parent[x]
}
unite := func(a, b int) {
a, b = find(a), find(b)
if a == b {
return
}
if size[a] < size[b] {
a, b = b, a
}
parent[b] = a
size[a] += size[b]
}
for acct, account := range accounts {
for i := 1; i < len(account); i++ {
email := account[i]
if _, ok := id[email]; !ok {
id[email] = len(emailOf)
emailOf = append(emailOf, email)
owner = append(owner, acct)
parent = append(parent, len(parent))
size = append(size, 1)
}
if i > 1 {
unite(id[account[1]], id[email]) // chain to the first email
}
}
}
groups := map[int][]string{} // root index -> its emails
for e := range emailOf {
root := find(e)
groups[root] = append(groups[root], emailOf[e])
}
ans := [][]string{}
for root, emails := range groups {
sort.Strings(emails)
merged := append([]string{accounts[owner[root]][0]}, emails...) // shared name rides along
ans = append(ans, merged)
}
return ans
}
// LC 721. Union-find over EMAILS: union every email with its account's first
// email, then group by root, sort, and prepend the shared name.
func accountsMerge(_ accounts: [[String]]) -> [[String]] {
var id: [String: Int] = [:] // email -> union-find index
var emailOf: [String] = [] // index -> email
var owner: [Int] = [] // index -> account that names this email
var parent: [Int] = []
var size: [Int] = []
func find(_ x: Int) -> Int {
var x = x
while parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
func unite(_ a: Int, _ b: Int) {
var a = find(a), b = find(b)
if a == b { return }
if size[a] < size[b] { swap(&a, &b) }
parent[b] = a
size[a] += size[b]
}
for (acct, account) in accounts.enumerated() {
for i in 1..<account.count {
let email = account[i]
if id[email] == nil {
id[email] = emailOf.count
emailOf.append(email)
owner.append(acct)
parent.append(parent.count)
size.append(1)
}
if i > 1 { unite(id[account[1]]!, id[email]!) } // chain to the first email
}
}
var groups: [Int: [String]] = [:] // root index -> its emails
for e in 0..<emailOf.count {
groups[find(e), default: []].append(emailOf[e])
}
var ans: [[String]] = []
for (root, emails) in groups {
ans.append([accounts[owner[root]][0]] + emails.sorted()) // shared name rides along
}
return ans
}
19. Evaluate Division
Medium · LC 399
Given equations like a / b = k with numeric values, answer queries for the ratio between two variables, or -1.0 when it cannot be derived. Build a weighted graph with an edge from a to b of weight k and a reverse edge of weight 1/k, then DFS from the numerator multiplying weights along the path to the denominator. The path product telescopes into the ratio; return -1.0 for unknown variables or disconnected pairs.
def calc_equation(
equations: list[list[str]], values: list[float], queries: list[list[str]]
// LC 399. Build a weighted graph: a / b = k gives an edge a -> b of weight k
// and a reverse edge b -> a of weight 1/k. Each query DFSes from numerator
// to denominator multiplying weights along the path -- the product
// telescopes into the ratio. Unknown variables or disconnected pairs answer
// -1.0; x / x for a KNOWN x is 1.0 via the trivial empty path. (-1.0 is a
// safe sentinel because all given values are positive.)
vector<double> calcEquation(vector<vector<string>> equations, vector<double> values,
vector<vector<string>> queries) {
unordered_map<string, vector<pair<string, double>>> graph;
for (size_t i = 0; i < equations.size(); ++i) {
graph[equations[i][0]].push_back({equations[i][1], values[i]});
graph[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});
}
vector<double> ans;
for (const auto& query : queries) {
const string& src = query[0];
const string& dst = query[1];
if (!graph.count(src) || !graph.count(dst)) { // unknown variable
ans.push_back(-1.0);
continue;
}
unordered_set<string> visited;
auto dfs = [&](auto&& self, const string& node, double product) -> double {
if (node == dst) return product; // path product = the ratio
visited.insert(node);
for (const auto& [next, weight] : graph[node])
if (!visited.count(next)) {
double result = self(self, next, product * weight);
if (result != -1.0) return result;
}
return -1.0;
};
ans.push_back(dfs(dfs, src, 1.0));
}
return ans;
}
/// LC 399. Weighted graph: a / b = k becomes an edge a -> b of weight k plus
/// the reverse edge of weight 1/k. DFS from numerator to denominator
/// multiplying weights; the path product telescopes into the ratio. Unknown
/// variables or disconnected pairs answer -1.0.
pub fn calc_equation(
equations: Vec<Vec<String>>,
values: Vec<f64>,
queries: Vec<Vec<String>>,
) -> Vec<f64> {
fn dfs<'a>(
graph: &HashMap<&'a str, Vec<(&'a str, f64)>>,
seen: &mut HashSet<&'a str>,
node: &'a str,
target: &str,
acc: f64,
) -> Option<f64> {
if node == target {
return Some(acc);
}
for &(next, weight) in &graph[node] {
if seen.insert(next) {
if let Some(ratio) = dfs(graph, seen, next, target, acc * weight) {
return Some(ratio);
}
}
}
None
}
let mut graph: HashMap<&str, Vec<(&str, f64)>> = HashMap::new();
for (eq, &k) in equations.iter().zip(values.iter()) {
graph.entry(&eq[0]).or_default().push((&eq[1], k));
graph.entry(&eq[1]).or_default().push((&eq[0], 1.0 / k));
}
queries
.iter()
.map(|q| {
let (a, b) = (q[0].as_str(), q[1].as_str());
if !graph.contains_key(a) || !graph.contains_key(b) {
return -1.0;
}
let mut seen = HashSet::from([a]);
dfs(&graph, &mut seen, a, b, 1.0).unwrap_or(-1.0)
})
.collect()
}
/** LC 399. Weighted graph: a->b of weight k plus b->a of weight 1/k; the DFS path product telescopes into the queried ratio, -1 if unknown or disconnected. */
export function calcEquation(
equations: string[][],
values: number[],
queries: string[][],
): number[] {
const graph = new Map<string, [string, number][]>();
function addEdge(from: string, to: string, weight: number): void {
let edges = graph.get(from);
if (!edges) {
edges = [];
graph.set(from, edges);
}
edges.push([to, weight]);
}
for (let i = 0; i < equations.length; i++) {
const [a, b] = equations[i];
addEdge(a, b, values[i]);
addEdge(b, a, 1 / values[i]);
}
function ratio(from: string, to: string): number {
if (!graph.has(from) || !graph.has(to)) return -1;
const visited = new Set<string>([from]);
function dfs(node: string, product: number): number {
if (node === to) return product; // handles from === to as 1.0 too
for (const [next, weight] of graph.get(node) ?? []) {
if (!visited.has(next)) {
visited.add(next);
const result = dfs(next, product * weight);
if (result !== -1) return result;
}
}
return -1;
}
return dfs(from, 1);
}
return queries.map(([a, b]) => ratio(a, b));
}
// LC 399. a/b = k is a weighted edge both ways (k and 1/k); a query DFS
// multiplies weights along the path and the products telescope into the ratio.
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
type edge struct {
to string
ratio float64
}
graph := map[string][]edge{}
for i, eq := range equations {
graph[eq[0]] = append(graph[eq[0]], edge{eq[1], values[i]})
graph[eq[1]] = append(graph[eq[1]], edge{eq[0], 1.0 / values[i]})
}
ans := make([]float64, 0, len(queries))
for _, query := range queries {
src, dst := query[0], query[1]
_, hasSrc := graph[src]
_, hasDst := graph[dst]
if !hasSrc || !hasDst { // unknown variable: nothing can be derived
ans = append(ans, -1.0)
continue
}
visited := map[string]bool{}
var dfs func(node string, product float64) float64
dfs = func(node string, product float64) float64 {
if node == dst {
return product // the path's ratios telescoped to src/dst
}
visited[node] = true
for _, e := range graph[node] {
if !visited[e.to] {
if result := dfs(e.to, product*e.ratio); result != -1.0 {
return result
}
}
}
return -1.0 // both known but disconnected
}
ans = append(ans, dfs(src, 1.0))
}
return ans
}
// LC 399. a / b = k is a weighted edge a -> b of weight k (plus the 1/k
// reverse); DFS multiplies weights so the path product telescopes into the
// queried ratio. Unknown variables or disconnected pairs answer -1.
func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
var graph: [String: [(String, Double)]] = [:]
for (i, eq) in equations.enumerated() {
graph[eq[0], default: []].append((eq[1], values[i]))
graph[eq[1], default: []].append((eq[0], 1.0 / values[i]))
}
var ans: [Double] = []
for query in queries {
let src = query[0], dst = query[1]
if graph[src] == nil || graph[dst] == nil { // unknown variable
ans.append(-1.0)
continue
}
var visited: Set<String> = []
func dfs(_ node: String, _ product: Double) -> Double {
if node == dst { return product } // the path's ratios telescoped
visited.insert(node)
for (next, weight) in graph[node] ?? [] where !visited.contains(next) {
let result = dfs(next, product * weight)
if result != -1.0 { return result }
}
return -1.0
}
ans.append(dfs(src, 1.0))
}
return ans
}
20. Minimum Height Trees
Medium · LC 310
Given a tree of n nodes as an undirected edge list, return all roots that minimize the resulting tree's height. Repeatedly peel off all current leaves layer by layer, like a reverse BFS from the outside in, until only one or two nodes remain. The survivors are the tree's centers and the answer; every tree has at most two centers, which is why one or two nodes always survive.
def find_min_height_trees(n: int, edges: list[list[int]]) -> list[int]:
"""LC 310. Minimum Height Trees.
The minimum-height roots are the tree's CENTERS. Peel off all
current leaves layer by layer, a reverse BFS from the outside in,
until one or two nodes remain -- every tree has at most two
centers, so one or two always survive. Decrement degrees instead of
rebuilding the graph; a node becomes a new leaf when its degree
drops to 1. O(V + E) time and space.
"""
if n <= 2:
return list(range(n)) # one or two nodes: every node is a center
graph: list[list[int]] = [[] for _ in range(n)]
degree = [0] * n
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
degree[a] += 1
degree[b] += 1
leaves = deque(node for node in range(n) if degree[node] == 1)
remaining = n
while remaining > 2: # stop while the centers are still standing
for _ in range(len(leaves)): # peel exactly one full layer per round
leaf = leaves.popleft()
remaining -= 1
for neighbor in graph[leaf]:
degree[neighbor] -= 1
if degree[neighbor] == 1:
leaves.append(neighbor) # exposed: a leaf of the next layer
return sorted(leaves)
// LC 310. The minimum-height roots are the tree's centers, of which every
// tree has one or two. Peel off all current leaves layer by layer -- a
// reverse BFS from the outside in -- enqueueing neighbors whose degree drops
// to 1, until at most two nodes remain; the survivors are the answer. A
// single node (n = 1) is its own center.
vector<int> findMinHeightTrees(int n, vector<vector<int>> edges) {
if (n == 1) return {0};
vector<vector<int>> graph(n);
vector<int> degree(n, 0);
for (const auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
++degree[e[0]];
++degree[e[1]];
}
vector<int> layer;
for (int node = 0; node < n; ++node)
if (degree[node] == 1) layer.push_back(node);
int remaining = n;
while (remaining > 2) { // at most two centers survive
remaining -= static_cast<int>(layer.size());
vector<int> nextLayer;
for (int leaf : layer)
for (int next : graph[leaf])
if (--degree[next] == 1) nextLayer.push_back(next);
layer = move(nextLayer);
}
return layer;
}
/// LC 310. Peel leaves layer by layer, a reverse BFS from the outside in,
/// until one or two nodes remain: those survivors are the tree's centers,
/// and every tree has at most two of them.
pub fn find_min_height_trees(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
if n <= 2 {
return (0..n as i32).collect();
}
let mut graph = vec![Vec::new(); n];
let mut degree = vec![0usize; n];
for e in &edges {
let (a, b) = (e[0] as usize, e[1] as usize);
graph[a].push(b);
graph[b].push(a);
degree[a] += 1;
degree[b] += 1;
}
let mut leaves: Vec<usize> = (0..n).filter(|&node| degree[node] == 1).collect();
let mut remaining = n;
while remaining > 2 {
remaining -= leaves.len();
let mut next = Vec::new();
for &leaf in &leaves {
for &nb in &graph[leaf] {
degree[nb] -= 1;
if degree[nb] == 1 {
next.push(nb);
}
}
}
leaves = next;
}
leaves.into_iter().map(|node| node as i32).collect()
}
/** LC 310. Peel all current leaves layer by layer, outside in; the one or two survivors are the tree's centers (no tree has more than two). */
export function findMinHeightTrees(n: number, edges: number[][]): number[] {
if (n === 1) return [0]; // node 0 has degree 0, so the leaf seed below would miss it
const graph: number[][] = Array.from({ length: n }, () => []);
const degree = new Array<number>(n).fill(0);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
degree[a]++;
degree[b]++;
}
let leaves: number[] = [];
for (let node = 0; node < n; node++) {
if (degree[node] === 1) leaves.push(node);
}
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const next: number[] = [];
for (const leaf of leaves) {
for (const nb of graph[leaf]) {
if (--degree[nb] === 1) next.push(nb);
}
}
leaves = next;
}
return leaves;
}
// LC 310. Peel leaf layers from the outside in (reverse BFS), decrementing
// degrees; the one or two surviving centers are the minimum-height roots.
func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{0} // a single node is its own center
}
graph := make([][]int, n)
degree := make([]int, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
graph[e[1]] = append(graph[e[1]], e[0])
degree[e[0]]++
degree[e[1]]++
}
layer := []int{}
for node := 0; node < n; node++ {
if degree[node] == 1 {
layer = append(layer, node)
}
}
remaining := n
for remaining > 2 { // at most two centers survive
remaining -= len(layer)
next := []int{}
for _, leaf := range layer {
for _, nb := range graph[leaf] {
degree[nb]--
if degree[nb] == 1 {
next = append(next, nb) // exposed: a leaf of the next layer
}
}
}
layer = next
}
return layer
}
// LC 310. The minimum-height roots are the tree's centers: peel off all current
// leaves layer by layer until at most two nodes -- the centers -- survive.
func findMinHeightTrees(_ n: Int, _ edges: [[Int]]) -> [Int] {
if n == 1 { return [0] } // a single node is its own center
var graph = [[Int]](repeating: [], count: n)
var degree = [Int](repeating: 0, count: n)
for e in edges {
graph[e[0]].append(e[1])
graph[e[1]].append(e[0])
degree[e[0]] += 1
degree[e[1]] += 1
}
var layer: [Int] = []
for node in 0..<n where degree[node] == 1 { layer.append(node) }
var remaining = n
while remaining > 2 { // at most two centers survive
remaining -= layer.count
var nextLayer: [Int] = []
for leaf in layer {
for next in graph[leaf] {
degree[next] -= 1
if degree[next] == 1 { nextLayer.append(next) } // exposed: next layer's leaf
}
}
layer = nextLayer
}
return layer
}
21. Word Ladder
Hard · LC 127
Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence changing one letter at a time through list words, or 0. BFS the implicit graph where words differing by one letter are adjacent, generating neighbors by substituting every position with every alphabet letter. Bidirectional BFS expanding the smaller frontier cuts the branching sharply; the answer counts words rather than steps, and endWord must appear in the list.
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
}