1. Path with Minimum Effort
Medium · LC 1631
Given a grid of heights, find a route from the top left to the bottom right minimizing the maximum absolute height difference between consecutive cells. Run Dijkstra where a path's cost is the largest step taken so far, popping the cell with the smallest such cost from a min-heap. The key change is relaxing with the max of current effort and the step difference instead of summing; binary search on effort plus BFS also works.
def minimum_effort_path(heights: list[list[int]]) -> int:
"""LC 1631. Path With Minimum Effort.
Dijkstra where a path's cost is its LARGEST single step, not the sum
of steps. The heap still pops the cheapest frontier cell first, so
the first time the bottom-right corner pops, its effort is optimal.
Only the relaxation changes: extending a path by one step costs
max(effort so far, |height difference|) instead of a running total.
O(mn log mn) time, O(mn) space.
"""
rows, cols = len(heights), len(heights[0])
inf = float("inf")
best: list[list[float]] = [[inf] * cols for _ in range(rows)]
best[0][0] = 0
heap: list[tuple[int, int, int]] = [(0, 0, 0)] # (effort, row, col)
while heap:
effort, r, c = heapq.heappop(heap)
if r == rows - 1 and c == cols - 1:
return effort
if effort > best[r][c]: # stale heap entry: a cheaper route got there first
continue
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols:
# modified relaxation: the new path's cost is the max of the
# old bottleneck and this step -- a minimax, never a sum
candidate = max(effort, abs(heights[nr][nc] - heights[r][c]))
if candidate < best[nr][nc]:
best[nr][nc] = candidate
heapq.heappush(heap, (candidate, nr, nc))
return 0 # unreachable: the corner always pops on a connected grid
// LC 1631. Dijkstra where a path's cost is the LARGEST step taken so far, not
// the sum: pop the cell with the smallest such cost from a min-heap and relax
// neighbors with max(current effort, |height difference|). Because the metric
// is a minimax, the first time the bottom-right cell pops, its effort is
// optimal. (Binary search on effort plus BFS also works.)
int minimumEffortPath(vector<vector<int>> heights) {
int rows = static_cast<int>(heights.size());
int cols = static_cast<int>(heights[0].size());
vector<vector<int>> effort(rows, vector<int>(cols, INT_MAX));
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
effort[0][0] = 0;
pq.emplace(0, 0, 0);
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [e, r, c] = pq.top();
pq.pop();
if (e > effort[r][c]) continue; // stale heap entry
if (r == rows - 1 && c == cols - 1) return e;
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) continue;
int ne = max(e, abs(heights[nr][nc] - heights[r][c])); // minimax relax
if (ne < effort[nr][nc]) {
effort[nr][nc] = ne;
pq.emplace(ne, nr, nc);
}
}
}
return 0;
}
/// LC 1631. Dijkstra where a path's cost is the LARGEST step taken so far,
/// not the sum: relax with max(effort, |height difference|) and pop the cell
/// with the smallest such maximum from a min-heap. The greedy pop is still
/// safe because the minimax metric is monotone along any path.
pub fn minimum_effort_path(heights: Vec<Vec<i32>>) -> i32 {
let (rows, cols) = (heights.len(), heights[0].len());
let mut best = vec![vec![i32::MAX; cols]; rows];
let mut heap = BinaryHeap::new();
best[0][0] = 0;
heap.push(Reverse((0, 0usize, 0usize)));
while let Some(Reverse((effort, r, c))) = heap.pop() {
if effort > best[r][c] {
continue; // stale heap entry
}
if r == rows - 1 && c == cols - 1 {
return effort;
}
for (dr, dc) in [(1isize, 0isize), (-1, 0), (0, 1), (0, -1)] {
let (nr, nc) = (r as isize + dr, c as isize + dc);
if nr < 0 || nc < 0 || nr as usize >= rows || nc as usize >= cols {
continue;
}
let (nr, nc) = (nr as usize, nc as usize);
let next = effort.max((heights[r][c] - heights[nr][nc]).abs());
if next < best[nr][nc] {
best[nr][nc] = next;
heap.push(Reverse((next, nr, nc)));
}
}
}
best[rows - 1][cols - 1]
}
/** LC 1631. Dijkstra where a path's cost is its largest step: relax with max(effort, diff), not a sum. */
export function minimumEffortPath(heights: number[][]): number {
const rows = heights.length;
const cols = heights[0].length;
const heap: [number, number, number][] = []; // [effort, row, col]; min-heap on effort
const push = (entry: [number, number, number]): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] <= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): [number, number, number] => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
return top;
};
const best = Array.from({ length: rows }, () => new Array<number>(cols).fill(Infinity));
best[0][0] = 0;
push([0, 0, 0]);
const moves = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
for (;;) {
const [effort, row, col] = pop();
if (row === rows - 1 && col === cols - 1) return effort; // first pop of the target is optimal
if (effort > best[row][col]) continue; // stale heap entry
for (const [dr, dc] of moves) {
const nr = row + dr;
const nc = col + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
// the path's effort is its worst single step, so take a max instead of adding
const next = Math.max(effort, Math.abs(heights[nr][nc] - heights[row][col]));
if (next < best[nr][nc]) {
best[nr][nc] = next;
push([next, nr, nc]);
}
}
}
}
// LC 1631. Dijkstra where a path's cost is its LARGEST step, not the sum:
// relax with max(effort so far, |height diff|); the first pop of the corner is optimal.
func minimumEffortPath(heights [][]int) int {
rows, cols := len(heights), len(heights[0])
const inf = 1<<31 - 1
effort := make([][]int, rows)
for r := range effort {
effort[r] = make([]int, cols)
for c := range effort[r] {
effort[r][c] = inf
}
}
heap := [][3]int{} // (effort, row, col) min-heap on effort
push := func(item [3]int) {
heap = append(heap, item)
for i := len(heap) - 1; i > 0; { // sift up
p := (i - 1) / 2
if heap[p][0] <= heap[i][0] {
break
}
heap[i], heap[p] = heap[p], heap[i]
i = p
}
}
pop := func() [3]int {
top := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
for i := 0; ; { // sift down
l, r, smallest := 2*i+1, 2*i+2, i
if l < len(heap) && heap[l][0] < heap[smallest][0] {
smallest = l
}
if r < len(heap) && heap[r][0] < heap[smallest][0] {
smallest = r
}
if smallest == i {
break
}
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
}
return top
}
effort[0][0] = 0
push([3]int{0, 0, 0})
for len(heap) > 0 {
item := pop()
e, r, c := item[0], item[1], item[2]
if e > effort[r][c] {
continue // stale heap entry
}
if r == rows-1 && c == cols-1 {
return e
}
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 {
continue
}
diff := heights[nr][nc] - heights[r][c]
if diff < 0 {
diff = -diff
}
ne := e // minimax relax: max of the old bottleneck and this step
if diff > ne {
ne = diff
}
if ne < effort[nr][nc] {
effort[nr][nc] = ne
push([3]int{ne, nr, nc})
}
}
}
return 0
}
// LC 1631. Dijkstra where a path's cost is its LARGEST single step, not the
// sum: relax with max(effort, |height difference|); first pop of the corner wins.
func minimumEffortPath(_ heights: [[Int]]) -> Int {
let rows = heights.count, cols = heights[0].count
var effort = [[Int]](repeating: [Int](repeating: Int.max, count: cols), count: rows)
var heap: [(Int, Int, Int)] = [] // (effort, row, col), min-heap on .0
func siftUp(_ start: Int) {
var child = start
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].0 <= heap[child].0 { break }
heap.swapAt(parent, child)
child = parent
}
}
func siftDown(_ start: Int) {
var parent = start
while true {
let left = 2 * parent + 1, right = left + 1
var smallest = parent
if left < heap.count && heap[left].0 < heap[smallest].0 { smallest = left }
if right < heap.count && heap[right].0 < heap[smallest].0 { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
}
func push(_ item: (Int, Int, Int)) {
heap.append(item)
siftUp(heap.count - 1)
}
func pop() -> (Int, Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
if !heap.isEmpty { siftDown(0) }
return top
}
effort[0][0] = 0
push((0, 0, 0))
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
while !heap.isEmpty {
let (e, r, c) = pop()
if e > effort[r][c] { continue } // stale heap entry
if r == rows - 1 && c == cols - 1 { return e }
for d in 0..<4 {
let nr = r + dr[d], nc = c + dc[d]
if nr < 0 || nr >= rows || nc < 0 || nc >= cols { continue }
let ne = max(e, abs(heights[nr][nc] - heights[r][c])) // minimax relax
if ne < effort[nr][nc] {
effort[nr][nc] = ne
push((ne, nr, nc))
}
}
}
return 0
}
2. Network Delay Time
Medium · LC 743
Given a directed weighted graph of n nodes and a starting node k, return the time for a signal from k to reach every node, or -1 if some node is unreachable. Run standard Dijkstra from k with a min-heap to get shortest distances to all nodes. The answer is the maximum of those distances, and any unreachable node, detected by a missing distance, forces the -1 result.
def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
"""LC 743. Network Delay Time.
Textbook Dijkstra from node k with a heapq min-heap. The first pop
of a node fixes its shortest distance (all weights are positive), so
later pops of the same node are simply skipped. The signal reaches
everyone when the LAST node hears it, so the answer is the maximum
finalized distance; fewer than n finalized nodes means somewhere is
unreachable. O(E log E) time, O(V + E) space.
"""
graph: dict[int, list[tuple[int, int]]] = defaultdict(list)
for source, target, weight in times:
graph[source].append((target, weight))
settled: dict[int, int] = {} # node -> final shortest distance from k
heap: list[tuple[int, int]] = [(0, k)]
while heap:
dist, node = heapq.heappop(heap)
if node in settled: # already finalized by an earlier (cheaper) pop
continue
settled[node] = dist
for nxt, weight in graph[node]:
if nxt not in settled:
heapq.heappush(heap, (dist + weight, nxt))
return max(settled.values()) if len(settled) == n else -1
// LC 743. Standard Dijkstra from k with a min-heap over (distance, node),
// skipping stale entries whose popped distance exceeds the recorded best. The
// answer is the maximum shortest distance over all nodes; any node left at
// infinity is unreachable and forces -1.
int networkDelayTime(vector<vector<int>> times, int n, int k) {
vector<vector<pair<int, int>>> adj(n + 1);
for (const auto& t : times) adj[t[0]].push_back({t[1], t[2]});
vector<int> dist(n + 1, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[k] = 0;
pq.emplace(0, k);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // stale heap entry
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.emplace(dist[v], v);
}
}
}
int ans = 0;
for (int v = 1; v <= n; ++v) {
if (dist[v] == INT_MAX) return -1; // unreachable node
ans = max(ans, dist[v]);
}
return ans;
}
/// LC 743. Standard Dijkstra from k with a min-heap of Reverse((dist, node)).
/// The answer is the maximum shortest distance over all nodes; any node still
/// at infinity is unreachable and forces -1.
pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
let n = n as usize;
let mut adj = vec![Vec::new(); n + 1];
for t in × {
adj[t[0] as usize].push((t[1] as usize, t[2]));
}
let mut dist = vec![i32::MAX; n + 1];
let mut heap = BinaryHeap::new();
dist[k as usize] = 0;
heap.push(Reverse((0, k as usize)));
while let Some(Reverse((d, u))) = heap.pop() {
if d > dist[u] {
continue; // stale heap entry
}
for &(v, w) in &adj[u] {
if d + w < dist[v] {
dist[v] = d + w;
heap.push(Reverse((d + w, v)));
}
}
}
let ans = *dist[1..=n].iter().max().unwrap();
if ans == i32::MAX { -1 } else { ans }
}
/** LC 743. Plain Dijkstra from k; the answer is the largest shortest distance, -1 if any node is unreached. */
export function networkDelayTime(times: number[][], n: number, k: number): number {
const next: [number, number][][] = Array.from({ length: n + 1 }, () => []); // node -> [neighbor, weight]
for (const [from, to, weight] of times) next[from].push([to, weight]);
const heap: [number, number][] = []; // [distance, node]; min-heap on distance
const push = (entry: [number, number]): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] <= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): [number, number] => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
return top;
};
const dist = new Array<number>(n + 1).fill(Infinity);
dist[k] = 0;
push([0, k]);
while (heap.length > 0) {
const [d, node] = pop();
if (d > dist[node]) continue; // stale heap entry
for (const [neighbor, weight] of next[node]) {
if (d + weight < dist[neighbor]) {
dist[neighbor] = d + weight;
push([d + weight, neighbor]);
}
}
}
let answer = 0;
for (let node = 1; node <= n; node++) answer = Math.max(answer, dist[node]); // signal arrives when the last node hears it
return answer === Infinity ? -1 : answer;
}
// LC 743. Textbook Dijkstra from k, skipping stale pops; the answer is the
// MAXIMUM shortest distance, and any node left at infinity forces -1.
func networkDelayTime(times [][]int, n int, k int) int {
const inf = 1<<31 - 1
adj := make([][][2]int, n+1) // node -> list of (neighbor, weight)
for _, t := range times {
adj[t[0]] = append(adj[t[0]], [2]int{t[1], t[2]})
}
dist := make([]int, n+1)
for i := range dist {
dist[i] = inf
}
heap := [][2]int{} // (distance, node) min-heap on distance
push := func(item [2]int) {
heap = append(heap, item)
for i := len(heap) - 1; i > 0; { // sift up
p := (i - 1) / 2
if heap[p][0] <= heap[i][0] {
break
}
heap[i], heap[p] = heap[p], heap[i]
i = p
}
}
pop := func() [2]int {
top := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
for i := 0; ; { // sift down
l, r, smallest := 2*i+1, 2*i+2, i
if l < len(heap) && heap[l][0] < heap[smallest][0] {
smallest = l
}
if r < len(heap) && heap[r][0] < heap[smallest][0] {
smallest = r
}
if smallest == i {
break
}
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
}
return top
}
dist[k] = 0
push([2]int{0, k})
for len(heap) > 0 {
item := pop()
d, u := item[0], item[1]
if d > dist[u] {
continue // stale heap entry
}
for _, e := range adj[u] {
v, w := e[0], e[1]
if d+w < dist[v] {
dist[v] = d + w
push([2]int{dist[v], v})
}
}
}
ans := 0
for v := 1; v <= n; v++ {
if dist[v] == inf {
return -1 // unreachable node
}
if dist[v] > ans {
ans = dist[v]
}
}
return ans
}
// LC 743. Textbook Dijkstra from k, skipping stale pops; the answer is the
// LARGEST finalized distance, and any node left at infinity forces -1.
func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
var adj = [[(Int, Int)]](repeating: [], count: n + 1) // node -> (neighbor, weight)
for t in times { adj[t[0]].append((t[1], t[2])) }
var dist = [Int](repeating: Int.max, count: n + 1)
var heap: [(Int, Int)] = [] // (distance, node), min-heap on .0
func siftUp(_ start: Int) {
var child = start
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].0 <= heap[child].0 { break }
heap.swapAt(parent, child)
child = parent
}
}
func siftDown(_ start: Int) {
var parent = start
while true {
let left = 2 * parent + 1, right = left + 1
var smallest = parent
if left < heap.count && heap[left].0 < heap[smallest].0 { smallest = left }
if right < heap.count && heap[right].0 < heap[smallest].0 { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
}
func push(_ item: (Int, Int)) {
heap.append(item)
siftUp(heap.count - 1)
}
func pop() -> (Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
if !heap.isEmpty { siftDown(0) }
return top
}
dist[k] = 0
push((0, k))
while !heap.isEmpty {
let (d, u) = pop()
if d > dist[u] { continue } // stale heap entry
for (v, w) in adj[u] where d + w < dist[v] {
dist[v] = d + w
push((dist[v], v))
}
}
var ans = 0
for v in 1...n {
if dist[v] == Int.max { return -1 } // unreachable node
ans = max(ans, dist[v])
}
return ans
}
3. Reconstruct Itinerary
Hard · LC 332
Given airline tickets as directed from-to pairs, reconstruct an itinerary starting at JFK that uses every ticket once, choosing the lexicographically smallest valid order. Sort or heap each airport's destinations, then run Hierholzer's algorithm: DFS greedily along unused edges and append an airport to the route only when its destinations are exhausted. The answer is the reversed postorder; pure greedy walking without the postorder trick can strand itself in a dead end.
def find_itinerary(tickets: list[list[str]]) -> list[str]:
"""LC 332. Reconstruct Itinerary.
Hierholzer's algorithm for an Eulerian path. Sorting the tickets in
REVERSE turns each airport's destination list into a stack whose
pop() always yields the lexicographically smallest unused ticket.
DFS greedily follows unused tickets and appends an airport to the
route only once its tickets are exhausted (postorder). A plain
greedy walk can strand itself in a dead end; the postorder trick
splices such dead ends back in, and reversing the postorder yields
the forward itinerary. O(E log E) time, O(E) space.
"""
destinations: dict[str, list[str]] = defaultdict(list)
for origin, dest in sorted(tickets, reverse=True): # reverse sort: pop() = smallest
destinations[origin].append(dest)
route: list[str] = []
def fly_until_stuck(airport: str) -> None:
while destinations[airport]:
fly_until_stuck(destinations[airport].pop())
route.append(airport) # postorder: recorded only when out of tickets
fly_until_stuck("JFK")
# the postorder lists airports in reverse visiting order (dead ends
# first), so reversing it produces the actual itinerary
return route[::-1]
// LC 332. Hierholzer's algorithm on the ticket multigraph: sort each airport's
// destinations ascending and keep a per-airport index pointer to the next
// unused ticket. DFS greedily along the smallest unused edge and append an
// airport only once its tickets are exhausted; the reversed postorder is the
// itinerary. Pure greedy walking can strand itself in a dead end -- the
// postorder trick splices dead-end detours back in at the right spot.
vector<string> findItinerary(vector<vector<string>> tickets) {
unordered_map<string, vector<string>> adj;
for (const auto& ticket : tickets) adj[ticket[0]].push_back(ticket[1]);
for (auto& entry : adj) sort(entry.second.begin(), entry.second.end());
unordered_map<string, int> nextIdx; // first unused ticket per airport
vector<string> route;
auto dfs = [&](auto&& self, const string& airport) -> void {
while (true) {
vector<string>& dests = adj[airport];
int& i = nextIdx[airport];
if (i >= static_cast<int>(dests.size())) break;
self(self, dests[i++]);
}
route.push_back(airport); // postorder: all tickets out are used
};
dfs(dfs, "JFK");
reverse(route.begin(), route.end());
return route;
}
/// LC 332. Hierholzer's algorithm over sorted adjacency lists with a per-node
/// next-edge index: walk greedily along unused edges, and append an airport
/// to the route only once its destinations are exhausted. The itinerary is
/// the reversed postorder; a plain greedy walk can strand itself in a dead
/// end, but postorder splices such detours back into the circuit.
pub fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
let mut adj: HashMap<String, Vec<String>> = HashMap::new();
for t in tickets {
adj.entry(t[0].clone()).or_default().push(t[1].clone());
}
for dests in adj.values_mut() {
dests.sort_unstable(); // lexicographic tie-break baked into edge order
}
let mut next: HashMap<String, usize> = HashMap::new();
let mut stack = vec!["JFK".to_string()];
let mut route = Vec::new();
while let Some(airport) = stack.last().cloned() {
let i = *next.get(&airport).unwrap_or(&0);
if let Some(dest) = adj.get(&airport).and_then(|d| d.get(i)) {
next.insert(airport, i + 1); // consume the ticket
stack.push(dest.clone());
} else {
route.push(stack.pop().unwrap()); // dead end: emit in postorder
}
}
route.reverse();
route
}
/** LC 332. Hierholzer: sorted destinations walked via next-edge indexes; the route is the reversed postorder. */
export function findItinerary(tickets: string[][]): string[] {
const destinationsOf = new Map<string, string[]>();
for (const [from, to] of tickets) {
let destinations = destinationsOf.get(from);
if (destinations === undefined) {
destinations = [];
destinationsOf.set(from, destinations);
}
destinations.push(to);
}
for (const destinations of destinationsOf.values()) destinations.sort(); // smallest airport first
const nextEdge = new Map<string, number>(); // airport -> first unused index in its sorted list
const route: string[] = [];
const stack = ["JFK"];
while (stack.length > 0) {
const airport = stack[stack.length - 1];
const destinations = destinationsOf.get(airport);
const next = nextEdge.get(airport) ?? 0;
if (destinations !== undefined && next < destinations.length) {
nextEdge.set(airport, next + 1); // consume the ticket before descending
stack.push(destinations[next]);
} else {
route.push(stack.pop()!); // exhausted airports finalize in postorder, so dead ends sink to the back
}
}
return route.reverse();
}
// LC 332. Hierholzer: always follow the smallest unused ticket, append an
// airport only once its tickets are exhausted (postorder), reverse at the end.
func findItinerary(tickets [][]string) []string {
adj := map[string][]string{}
for _, ticket := range tickets {
adj[ticket[0]] = append(adj[ticket[0]], ticket[1])
}
for _, dests := range adj {
sort.Strings(dests)
}
nextIdx := map[string]int{} // first unused ticket per airport
route := []string{}
var visit func(airport string)
visit = func(airport string) {
for nextIdx[airport] < len(adj[airport]) {
dest := adj[airport][nextIdx[airport]]
nextIdx[airport]++
visit(dest)
}
route = append(route, airport) // postorder: all tickets out are used
}
visit("JFK")
for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
route[i], route[j] = route[j], route[i] // reversed postorder = itinerary
}
return route
}
// LC 332. Hierholzer: DFS along the smallest unused ticket (sorted lists plus a
// per-airport index) and record each airport in POSTORDER; the reversed
// postorder splices dead-end detours back into the itinerary.
func findItinerary(_ tickets: [[String]]) -> [String] {
var adj: [String: [String]] = [:]
for ticket in tickets { adj[ticket[0], default: []].append(ticket[1]) }
for key in Array(adj.keys) { adj[key]!.sort() }
var nextIdx: [String: Int] = [:] // first unused ticket per airport
var route: [String] = []
func dfs(_ airport: String) {
while let dests = adj[airport], nextIdx[airport, default: 0] < dests.count {
let i = nextIdx[airport, default: 0]
nextIdx[airport] = i + 1
dfs(dests[i])
}
route.append(airport) // postorder: all tickets out are used
}
dfs("JFK")
return Array(route.reversed())
}
4. Min Cost to Connect All Points
Medium · LC 1584
Given points on a plane, connect them all at minimum total cost, where an edge costs the Manhattan distance between its endpoints. Build a minimum spanning tree with Prim's algorithm, growing from one point and repeatedly absorbing the cheapest outside point via a min-heap or a distance array. Because the graph is complete with O(n^2) edges, the array form of Prim's is the natural fit, though Kruskal with union-find also passes.
def min_cost_connect_points(points: list[list[int]]) -> int:
"""LC 1584. Min Cost to Connect All Points.
Prim's algorithm over the complete graph of Manhattan distances.
Grow the tree from point 0; each time a point joins, push the
distance from it to every point still outside. The heap always pops
the cheapest edge crossing the tree boundary, and a visited set
discards stale entries for points absorbed earlier via a cheaper
edge. O(n^2 log n) time, O(n^2) space.
"""
n = len(points)
in_tree: set[int] = set()
heap: list[tuple[int, int]] = [(0, 0)] # (cost to attach, point index)
total = 0
while len(in_tree) < n:
cost, i = heapq.heappop(heap)
if i in in_tree: # stale: this point already joined more cheaply
continue
in_tree.add(i)
total += cost
x, y = points[i]
for j in range(n):
if j not in in_tree:
manhattan = abs(x - points[j][0]) + abs(y - points[j][1])
heapq.heappush(heap, (manhattan, j))
return total
// LC 1584. Prim's algorithm in array form: keep, for every point outside the
// tree, the cheapest Manhattan edge into the tree, then absorb the closest
// outside point and refresh the array against it. The graph is complete with
// O(n^2) edges, so the O(n^2) scan beats a heap here; Kruskal with union-find
// also passes.
int minCostConnectPoints(vector<vector<int>> points) {
int n = static_cast<int>(points.size());
vector<int> minEdge(n, INT_MAX);
vector<bool> inTree(n, false);
minEdge[0] = 0;
int total = 0;
for (int round = 0; round < n; ++round) {
int u = -1;
for (int v = 0; v < n; ++v)
if (!inTree[v] && (u == -1 || minEdge[v] < minEdge[u])) u = v;
inTree[u] = true;
total += minEdge[u];
for (int v = 0; v < n; ++v) {
if (inTree[v]) continue;
int d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
if (d < minEdge[v]) minEdge[v] = d;
}
}
return total;
}
/// LC 1584. Array-form Prim's: keep each outside point's cheapest Manhattan
/// distance into the growing tree, absorb the closest one, then relax the
/// rest against the new member. The graph is complete with O(n^2) edges, so
/// the O(n^2) distance array beats a heap here.
pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut in_tree = vec![false; n];
let mut dist = vec![i32::MAX; n];
dist[0] = 0;
let mut total = 0;
for _ in 0..n {
let u = (0..n).filter(|&i| !in_tree[i]).min_by_key(|&i| dist[i]).unwrap();
in_tree[u] = true;
total += dist[u];
for v in 0..n {
if !in_tree[v] {
let d = (points[u][0] - points[v][0]).abs()
+ (points[u][1] - points[v][1]).abs();
dist[v] = dist[v].min(d);
}
}
}
total
}
/** LC 1584. Array-form Prim's: the graph is complete, so an O(n^2) nearest-outside-point scan beats a heap. */
export function minCostConnectPoints(points: number[][]): number {
const n = points.length;
const minDist = new Array<number>(n).fill(Infinity); // cheapest edge from the tree to each outside point
const inTree = new Array<boolean>(n).fill(false);
minDist[0] = 0;
let total = 0;
for (let added = 0; added < n; added++) {
let best = -1;
for (let i = 0; i < n; i++) {
if (!inTree[i] && (best === -1 || minDist[i] < minDist[best])) best = i;
}
inTree[best] = true;
total += minDist[best];
for (let i = 0; i < n; i++) {
if (inTree[i]) continue;
// absorbing `best` may give outside points a cheaper attachment edge
const dist = Math.abs(points[i][0] - points[best][0]) + Math.abs(points[i][1] - points[best][1]);
if (dist < minDist[i]) minDist[i] = dist;
}
}
return total;
}
// LC 1584. Prim in array form: absorb the cheapest outside point, then refresh
// each outsider's best edge into the tree; O(n^2) beats a heap on a complete graph.
func minCostConnectPoints(points [][]int) int {
abs := func(x int) int {
if x < 0 {
return -x
}
return x
}
n := len(points)
const inf = 1<<31 - 1
minEdge := make([]int, n) // cheapest known edge from each point into the tree
inTree := make([]bool, n)
for i := range minEdge {
minEdge[i] = inf
}
minEdge[0] = 0
total := 0
for round := 0; round < n; round++ {
u := -1
for v := 0; v < n; v++ {
if !inTree[v] && (u == -1 || minEdge[v] < minEdge[u]) {
u = v // the cheapest outsider joins the tree
}
}
inTree[u] = true
total += minEdge[u]
for v := 0; v < n; v++ {
if inTree[v] {
continue
}
d := abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
if d < minEdge[v] {
minEdge[v] = d
}
}
}
return total
}
// LC 1584. Prim in array form: track each outside point's cheapest Manhattan
// edge into the tree, absorb the closest outsider, refresh against it. The
// graph is complete, so the O(n^2) scan beats a heap.
func minCostConnectPoints(_ points: [[Int]]) -> Int {
let n = points.count
var minEdge = [Int](repeating: Int.max, count: n)
var inTree = [Bool](repeating: false, count: n)
minEdge[0] = 0
var total = 0
for _ in 0..<n {
var u = -1
for v in 0..<n where !inTree[v] && (u == -1 || minEdge[v] < minEdge[u]) { u = v }
inTree[u] = true
total += minEdge[u]
for v in 0..<n where !inTree[v] {
let d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
if d < minEdge[v] { minEdge[v] = d }
}
}
return total
}
5. Swim In Rising Water
Hard · LC 778
Given an n by n grid of elevations, find the minimum time t that permits swimming from top left to bottom right through cells of elevation at most t. Run Dijkstra where a path's cost is the maximum elevation seen, expanding the cell with the smallest such maximum from a min-heap. The cost is a minimax, not a sum; binary search on t with BFS, or union-find adding cells in elevation order, also work.
def swim_in_water(grid: list[list[int]]) -> int:
"""LC 778. Swim in Rising Water.
Dijkstra where a path's cost is the HIGHEST elevation it crosses --
the minimum time t to reach a cell is the smallest possible maximum
along any route. Pop the cell with the lowest such maximum; the
first pop of the bottom-right corner is the answer. Marking visited
on push is safe here because a cell's key, max(popped time, its own
elevation), can never improve once any route reaches it: later pops
only carry equal or larger times. O(n^2 log n) time, O(n^2) space.
"""
n = len(grid)
heap: list[tuple[int, int, int]] = [(grid[0][0], 0, 0)] # (time, row, col)
seen: set[tuple[int, int]] = {(0, 0)}
while heap:
time, r, c = heapq.heappop(heap)
if r == n - 1 and c == n - 1:
return time
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
# minimax relaxation: wait for the deeper of "water level so
# far" and this cell's own elevation
heapq.heappush(heap, (max(time, grid[nr][nc]), nr, nc))
return -1 # unreachable: the grid is connected, the corner always pops
// LC 778. Dijkstra where a path's cost is the maximum elevation seen along it:
// expand the cell with the smallest such maximum from a min-heap, relaxing
// neighbors with max(cost so far, neighbor elevation). The cost is a minimax,
// not a sum, so the first pop of the bottom-right cell is the answer. (Binary
// search on t with BFS, or union-find adding cells by elevation, also work.)
int swimInWater(vector<vector<int>> grid) {
int n = static_cast<int>(grid.size());
vector<vector<int>> best(n, vector<int>(n, INT_MAX));
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
best[0][0] = grid[0][0];
pq.emplace(grid[0][0], 0, 0);
const int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (!pq.empty()) {
auto [t, r, c] = pq.top();
pq.pop();
if (t > best[r][c]) continue; // stale heap entry
if (r == n - 1 && c == n - 1) return t;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
int nt = max(t, grid[nr][nc]); // minimax relax
if (nt < best[nr][nc]) {
best[nr][nc] = nt;
pq.emplace(nt, nr, nc);
}
}
}
return 0;
}
/// LC 778. Dijkstra where a path's cost is the maximum elevation seen so far:
/// relax with max(time, neighbor's elevation) and pop the cell with the
/// smallest such maximum. Same minimax twist as LC 1631, only the cost lives
/// on cells instead of edges.
pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let mut best = vec![vec![i32::MAX; n]; n];
let mut heap = BinaryHeap::new();
best[0][0] = grid[0][0];
heap.push(Reverse((grid[0][0], 0usize, 0usize)));
while let Some(Reverse((t, r, c))) = heap.pop() {
if t > best[r][c] {
continue; // stale heap entry
}
if r == n - 1 && c == n - 1 {
return t;
}
for (dr, dc) in [(1isize, 0isize), (-1, 0), (0, 1), (0, -1)] {
let (nr, nc) = (r as isize + dr, c as isize + dc);
if nr < 0 || nc < 0 || nr as usize >= n || nc as usize >= n {
continue;
}
let (nr, nc) = (nr as usize, nc as usize);
let next = t.max(grid[nr][nc]);
if next < best[nr][nc] {
best[nr][nc] = next;
heap.push(Reverse((next, nr, nc)));
}
}
}
best[n - 1][n - 1]
}
/** LC 778. Dijkstra where a path's cost is the highest elevation touched: a minimax, so relax with max. */
export function swimInWater(grid: number[][]): number {
const n = grid.length;
const heap: [number, number, number][] = []; // [max elevation so far, row, col]; min-heap on elevation
const push = (entry: [number, number, number]): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] <= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): [number, number, number] => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
return top;
};
const best = Array.from({ length: n }, () => new Array<number>(n).fill(Infinity));
best[0][0] = grid[0][0]; // the start cell itself must be underwater
push([grid[0][0], 0, 0]);
const moves = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
for (;;) {
const [elevation, row, col] = pop();
if (row === n - 1 && col === n - 1) return elevation; // first pop of the target is optimal
if (elevation > best[row][col]) continue; // stale heap entry
for (const [dr, dc] of moves) {
const nr = row + dr;
const nc = col + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
const next = Math.max(elevation, grid[nr][nc]); // water must cover the deepest cell on the route
if (next < best[nr][nc]) {
best[nr][nc] = next;
push([next, nr, nc]);
}
}
}
}
// LC 778. Dijkstra where a path's cost is the HIGHEST elevation it crosses:
// relax with max(time so far, neighbor elevation); first pop of the corner wins.
func swimInWater(grid [][]int) int {
n := len(grid)
const inf = 1<<31 - 1
best := make([][]int, n)
for r := range best {
best[r] = make([]int, n)
for c := range best[r] {
best[r][c] = inf
}
}
heap := [][3]int{} // (time, row, col) min-heap on time
push := func(item [3]int) {
heap = append(heap, item)
for i := len(heap) - 1; i > 0; { // sift up
p := (i - 1) / 2
if heap[p][0] <= heap[i][0] {
break
}
heap[i], heap[p] = heap[p], heap[i]
i = p
}
}
pop := func() [3]int {
top := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
for i := 0; ; { // sift down
l, r, smallest := 2*i+1, 2*i+2, i
if l < len(heap) && heap[l][0] < heap[smallest][0] {
smallest = l
}
if r < len(heap) && heap[r][0] < heap[smallest][0] {
smallest = r
}
if smallest == i {
break
}
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
}
return top
}
best[0][0] = grid[0][0]
push([3]int{grid[0][0], 0, 0})
for len(heap) > 0 {
item := pop()
t, r, c := item[0], item[1], item[2]
if t > best[r][c] {
continue // stale heap entry
}
if r == n-1 && c == n-1 {
return t
}
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 >= n || nc < 0 || nc >= n {
continue
}
nt := t // minimax relax: wait for the deeper of level and elevation
if grid[nr][nc] > nt {
nt = grid[nr][nc]
}
if nt < best[nr][nc] {
best[nr][nc] = nt
push([3]int{nt, nr, nc})
}
}
}
return 0
}
// LC 778. Dijkstra where a path's cost is the HIGHEST elevation it crosses:
// relax with max(time, neighbor elevation); first pop of the far corner wins.
func swimInWater(_ grid: [[Int]]) -> Int {
let n = grid.count
var best = [[Int]](repeating: [Int](repeating: Int.max, count: n), count: n)
var heap: [(Int, Int, Int)] = [] // (time, row, col), min-heap on .0
func siftUp(_ start: Int) {
var child = start
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].0 <= heap[child].0 { break }
heap.swapAt(parent, child)
child = parent
}
}
func siftDown(_ start: Int) {
var parent = start
while true {
let left = 2 * parent + 1, right = left + 1
var smallest = parent
if left < heap.count && heap[left].0 < heap[smallest].0 { smallest = left }
if right < heap.count && heap[right].0 < heap[smallest].0 { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
}
func push(_ item: (Int, Int, Int)) {
heap.append(item)
siftUp(heap.count - 1)
}
func pop() -> (Int, Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
if !heap.isEmpty { siftDown(0) }
return top
}
best[0][0] = grid[0][0]
push((grid[0][0], 0, 0))
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]
while !heap.isEmpty {
let (t, r, c) = pop()
if t > best[r][c] { continue } // stale heap entry
if r == n - 1 && c == n - 1 { return t }
for d in 0..<4 {
let nr = r + dr[d], nc = c + dc[d]
if nr < 0 || nr >= n || nc < 0 || nc >= n { continue }
let nt = max(t, grid[nr][nc]) // minimax relax
if nt < best[nr][nc] {
best[nr][nc] = nt
push((nt, nr, nc))
}
}
}
return 0
}
6. Alien Dictionary
Hard · LC 269
Given a list of words sorted in an unknown alien alphabet, return any valid ordering of the letters, or an empty string if none exists. Compare each adjacent pair of words, taking the first differing characters as a directed edge, then topologically sort the letter graph with Kahn's BFS or DFS. Watch the invalid prefix case where a longer word precedes its own prefix, and a cycle in the graph also means no answer.
def alien_order(words: list[str]) -> str:
"""LC 269. Alien Dictionary.
Each adjacent word pair contributes at most one edge: the first
position where the words differ orders those two letters. Kahn's
BFS then topologically sorts the letters. Two invalid shapes return
"": a longer word sorted BEFORE its own prefix (no first difference
exists, yet the order claims longer < shorter), and a cycle, which
leaves letters with nonzero indegree out of the output. O(total
letters) time, O(unique letters^2) space.
"""
graph: dict[str, set[str]] = {ch: set() for word in words for ch in word}
indegree: dict[str, int] = {ch: 0 for ch in graph}
for first, second in zip(words, words[1:]):
for a, b in zip(first, second):
if a != b:
if b not in graph[a]: # dedupe so indegree counts each edge once
graph[a].add(b)
indegree[b] += 1
break
else: # no differing position: one word is a prefix of the other
if len(second) < len(first):
return "" # a word listed after its own extension is impossible
queue = deque(ch for ch in graph if indegree[ch] == 0)
order: list[str] = []
while queue:
ch = queue.popleft()
order.append(ch)
for nxt in graph[ch]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return "".join(order) if len(order) == len(graph) else "" # leftovers = cycle
// LC 269. Compare each ADJACENT pair of words; the first differing characters
// give a directed edge, then Kahn's BFS topologically sorts the letter graph
// (seeding zero in-degree letters alphabetically keeps the output here
// deterministic). Two failure modes return "": a longer word preceding its own
// prefix, and a cycle, detected when the sort emits fewer letters than exist.
string alienOrder(vector<string> words) {
vector<int> indeg(26, -1); // -1 marks letters absent from the alphabet
for (const string& word : words)
for (char ch : word)
if (indeg[ch - 'a'] == -1) indeg[ch - 'a'] = 0;
vector<unordered_set<int>> adj(26);
for (int i = 0; i + 1 < static_cast<int>(words.size()); ++i) {
const string& a = words[i];
const string& b = words[i + 1];
int len = static_cast<int>(min(a.size(), b.size()));
int j = 0;
while (j < len && a[j] == b[j]) ++j;
if (j == len) {
if (a.size() > b.size()) return ""; // invalid: word precedes its own prefix
continue;
}
int u = a[j] - 'a', v = b[j] - 'a';
if (!adj[u].count(v)) { // first differing characters form an edge
adj[u].insert(v);
++indeg[v];
}
}
queue<int> q;
int present = 0;
for (int c = 0; c < 26; ++c) {
if (indeg[c] == -1) continue;
++present;
if (indeg[c] == 0) q.push(c);
}
string order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(static_cast<char>('a' + u));
for (int v : adj[u])
if (--indeg[v] == 0) q.push(v);
}
return static_cast<int>(order.size()) == present ? order : ""; // short output = cycle
}
/// LC 269. Each adjacent word pair contributes one edge: the first differing
/// characters order those two letters. Kahn's BFS over the letters that
/// actually appear then yields an alphabet; leftover letters mean a cycle and
/// no answer. The trap is the prefix case -- a longer word sorted before its
/// own prefix is invalid before any edges are even drawn.
pub fn alien_order(words: Vec<String>) -> String {
let mut present = [false; 26];
let mut edge = [[false; 26]; 26];
let mut indegree = [0i32; 26];
for w in &words {
for &b in w.as_bytes() {
present[(b - b'a') as usize] = true;
}
}
for pair in words.windows(2) {
let (a, b) = (pair[0].as_bytes(), pair[1].as_bytes());
let mut i = 0;
while i < a.len() && i < b.len() && a[i] == b[i] {
i += 1;
}
if i == b.len() && i < a.len() {
return String::new(); // "abc" before "ab": invalid prefix order
}
if i < a.len() && i < b.len() {
let (u, v) = ((a[i] - b'a') as usize, (b[i] - b'a') as usize);
if !edge[u][v] {
edge[u][v] = true;
indegree[v] += 1;
}
}
}
let mut queue: VecDeque<usize> =
(0..26).filter(|&c| present[c] && indegree[c] == 0).collect();
let mut order = String::new();
while let Some(u) = queue.pop_front() {
order.push((b'a' + u as u8) as char);
for v in 0..26 {
if edge[u][v] {
indegree[v] -= 1;
if indegree[v] == 0 {
queue.push_back(v);
}
}
}
}
let total = present.iter().filter(|&&p| p).count();
if order.len() == total { order } else { String::new() } // cycle check
}
/** LC 269. First differing chars of adjacent words form edges; Kahn's BFS orders them. Prefix case and cycles return "". */
export function alienOrder(words: string[]): string {
const next = new Map<string, Set<string>>();
const indegree = new Map<string, number>();
for (const word of words) {
for (const ch of word) {
if (!indegree.has(ch)) {
indegree.set(ch, 0);
next.set(ch, new Set());
}
}
}
for (let i = 1; i < words.length; i++) {
const prev = words[i - 1];
const curr = words[i];
const minLen = Math.min(prev.length, curr.length);
let j = 0;
while (j < minLen && prev[j] === curr[j]) j++;
if (j === minLen) {
if (prev.length > curr.length) return ""; // a word before its own prefix can never be sorted
continue; // identical up to the shorter word: no information
}
const from = prev[j];
const to = curr[j];
if (!next.get(from)!.has(to)) {
next.get(from)!.add(to); // only the first mismatch orders the pair; later chars say nothing
indegree.set(to, indegree.get(to)! + 1);
}
}
const queue: string[] = [];
for (const [ch, degree] of indegree) {
if (degree === 0) queue.push(ch);
}
const order: string[] = [];
for (let head = 0; head < queue.length; head++) {
const ch = queue[head];
order.push(ch);
for (const to of next.get(ch)!) {
const degree = indegree.get(to)! - 1;
indegree.set(to, degree);
if (degree === 0) queue.push(to);
}
}
return order.length === indegree.size ? order.join("") : ""; // letters left over means a cycle
}
// LC 269. Adjacent words make one edge each at their first differing letters;
// Kahn's topo sort orders the alphabet. Prefix violations and cycles return "".
func alienOrder(words []string) string {
var indeg [26]int // -1 marks letters absent from the alphabet
for i := range indeg {
indeg[i] = -1
}
for _, word := range words {
for _, ch := range word {
if indeg[ch-'a'] == -1 {
indeg[ch-'a'] = 0
}
}
}
var adj [26][26]bool
for i := 0; i+1 < len(words); i++ {
a, b := words[i], words[i+1]
minLen := len(a)
if len(b) < minLen {
minLen = len(b)
}
j := 0
for j < minLen && a[j] == b[j] {
j++
}
if j == minLen {
if len(a) > len(b) {
return "" // invalid: word precedes its own prefix
}
continue
}
u, v := int(a[j]-'a'), int(b[j]-'a')
if !adj[u][v] { // first differing characters form an edge, deduped
adj[u][v] = true
indeg[v]++
}
}
queue := []int{}
present := 0
for c := 0; c < 26; c++ {
if indeg[c] == -1 {
continue
}
present++
if indeg[c] == 0 {
queue = append(queue, c) // alphabetical seeding keeps output deterministic
}
}
order := []byte{}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
order = append(order, byte('a'+u))
for v := 0; v < 26; v++ {
if adj[u][v] {
indeg[v]--
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
}
if len(order) != present {
return "" // letters left with nonzero indegree: cycle
}
return string(order)
}
// LC 269. The first differing letters of each adjacent word pair form an edge;
// Kahn's BFS topo-sorts the alphabet. A word before its own prefix, or a
// cycle (short output), returns "".
func alienOrder(_ words: [String]) -> String {
var indeg = [Int](repeating: -1, count: 26) // -1 marks letters absent from the alphabet
let codes = words.map { $0.utf8.map { Int($0) - 97 } }
for word in codes {
for ch in word where indeg[ch] == -1 { indeg[ch] = 0 }
}
var adj = [[Bool]](repeating: [Bool](repeating: false, count: 26), count: 26)
for i in 0..<(codes.count - 1) {
let a = codes[i], b = codes[i + 1]
let len = min(a.count, b.count)
var j = 0
while j < len && a[j] == b[j] { j += 1 }
if j == len {
if a.count > b.count { return "" } // invalid: word precedes its own prefix
continue
}
if !adj[a[j]][b[j]] { // dedupe so indegree counts each edge once
adj[a[j]][b[j]] = true
indeg[b[j]] += 1
}
}
var queue: [Int] = []
var present = 0
for c in 0..<26 where indeg[c] != -1 {
present += 1
if indeg[c] == 0 { queue.append(c) }
}
var head = 0
var order = ""
while head < queue.count {
let u = queue[head]
head += 1
order.append(Character(UnicodeScalar(UInt8(97 + u))))
for v in 0..<26 where adj[u][v] {
indeg[v] -= 1
if indeg[v] == 0 { queue.append(v) }
}
}
return order.count == present ? order : "" // short output = cycle
}
7. Cheapest Flights Within K Stops
Medium · LC 787
Given flights as directed weighted edges, find the cheapest price from src to dst using at most k intermediate stops, or -1 if impossible. Run Bellman-Ford for exactly k+1 rounds, relaxing every edge each round, but read distances from a snapshot copied at the start of the round. The snapshot is the trick: it stops multiple edges from chaining within one round, so round i holds the best price using at most i edges.
def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
"""LC 787. Cheapest Flights Within K Stops.
Bellman-Ford run for exactly k+1 rounds (k stops = at most k+1
edges), relaxing every flight each round but READING from a snapshot
copied at the start of the round. The snapshot is the whole trick:
relaxing against live prices would let several flights chain inside
a single round, sneaking in paths longer than the round's edge
budget. With the snapshot, round i holds the best price using at
most i edges. O(k * E) time, O(V) space.
"""
inf = float("inf")
prices: list[float] = [inf] * n
prices[src] = 0
for _ in range(k + 1):
previous = prices[:] # snapshot: prices reachable with one fewer edge
for u, v, price in flights:
if previous[u] == inf:
continue
# relax from the SNAPSHOT, never from this round's updates --
# otherwise u -> v -> w could both apply in one round and the
# path would use more edges than the round allows
if previous[u] + price < prices[v]:
prices[v] = previous[u] + price
return -1 if prices[dst] == inf else int(prices[dst])
// LC 787. Bellman-Ford run for exactly k+1 rounds, relaxing every edge each
// round but READING from a snapshot copied at the start of the round. The
// snapshot is the trick: it stops several edges from chaining within a single
// round, so after round i the table holds the best price using at most i+1
// edges (i intermediate stops).
int findCheapestPrice(int n, vector<vector<int>> flights, int src, int dst, int k) {
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n, INF);
dist[src] = 0;
for (int round = 0; round <= k; ++round) { // k+1 rounds total
vector<long long> snapshot = dist;
bool changed = false;
for (const auto& f : flights) {
if (snapshot[f[0]] + f[2] < dist[f[1]]) { // read snapshot, write dist
dist[f[1]] = snapshot[f[0]] + f[2];
changed = true;
}
}
if (!changed) break;
}
return dist[dst] == INF ? -1 : static_cast<int>(dist[dst]);
}
/// LC 787. Bellman-Ford run for exactly k + 1 rounds, relaxing every edge
/// against a snapshot of the previous round's distances. The snapshot is the
/// whole trick: relaxing against the live array would let several edges chain
/// inside one round, breaking the invariant that after round i each distance
/// uses at most i edges -- and at most i edges is exactly the "at most k
/// stops" budget.
pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
let mut dist = vec![i32::MAX; n as usize];
dist[src as usize] = 0;
for _ in 0..=k {
let prev = dist.clone(); // snapshot: this round only sees last round
for f in &flights {
let (u, v, w) = (f[0] as usize, f[1] as usize, f[2]);
if prev[u] != i32::MAX && prev[u] + w < dist[v] {
dist[v] = prev[u] + w;
}
}
}
if dist[dst as usize] == i32::MAX { -1 } else { dist[dst as usize] }
}
/** LC 787. Bellman-Ford for k + 1 rounds, reading from a snapshot so one round adds at most one edge. */
export function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
let dist = new Array<number>(n).fill(Infinity);
dist[src] = 0;
for (let round = 0; round <= k; round++) {
const relaxed = [...dist]; // write here, read from `dist`: edges cannot chain within a round
for (const [from, to, price] of flights) {
if (dist[from] !== Infinity && dist[from] + price < relaxed[to]) {
relaxed[to] = dist[from] + price;
}
}
dist = relaxed; // after round i, dist holds the best price using at most i + 1 edges
}
return dist[dst] === Infinity ? -1 : dist[dst];
}
// LC 787. Bellman-Ford for exactly k+1 rounds, relaxing every flight off a
// SNAPSHOT so edges cannot chain within one round and exceed the edge budget.
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
const inf = 1<<31 - 1
prices := make([]int, n)
for i := range prices {
prices[i] = inf
}
prices[src] = 0
for round := 0; round <= k; round++ { // k stops = at most k+1 edges
snapshot := append([]int(nil), prices...)
for _, f := range flights {
if snapshot[f[0]] == inf {
continue
}
if snapshot[f[0]]+f[2] < prices[f[1]] { // read snapshot, write prices
prices[f[1]] = snapshot[f[0]] + f[2]
}
}
}
if prices[dst] == inf {
return -1
}
return prices[dst]
}
// LC 787. Bellman-Ford for exactly k+1 rounds, relaxing every flight against a
// SNAPSHOT of the round's start so no two flights can chain within one round.
func findCheapestPrice(_ n: Int, _ flights: [[Int]], _ src: Int, _ dst: Int, _ k: Int) -> Int {
let inf = Int.max / 4
var dist = [Int](repeating: inf, count: n)
dist[src] = 0
for _ in 0...k { // k+1 rounds total
let snapshot = dist // prices reachable with one fewer edge
var changed = false
for f in flights where snapshot[f[0]] + f[2] < dist[f[1]] { // read snapshot, write dist
dist[f[1]] = snapshot[f[0]] + f[2]
changed = true
}
if !changed { break }
}
return dist[dst] == inf ? -1 : dist[dst]
}
8. Find Critical and Pseudo Critical Edges in Minimum Spanning Tree
Hard · LC 1489
Given a weighted undirected graph, classify each edge as critical, meaning every MST must include it, or pseudo-critical, meaning some MST can include it. First compute the baseline MST weight with Kruskal, then for each edge rerun Kruskal once with that edge excluded and once with it forced in first. Exclusion raising the weight or disconnecting the graph marks critical; forcing it in while matching the baseline weight marks pseudo-critical.
def find_critical_and_pseudo_critical_edges(n: int, edges: list[list[int]]) -> list[list[int]]:
"""LC 1489. Find Critical and Pseudo-Critical Edges in MST.
Kruskal once for the baseline MST weight, then interrogate each edge
with two more Kruskal runs: EXCLUDE it -- if the weight rises or the
graph disconnects, every MST needs it (critical); otherwise FORCE it
in first -- if the weight still matches the baseline, some MST can
use it (pseudo-critical). Union-find with path halving backs each
run. O(E^2 alpha(V)) time after the O(E log E) sort, O(V + E) space.
"""
order = sorted(range(len(edges)), key=lambda i: edges[i][2]) # indices by weight
def kruskal(skipped: int, forced: int) -> float:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(a: int, b: int) -> bool:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return False # already connected: edge would close a cycle
parent[root_a] = root_b
return True
weight = 0
components = n
if forced != -1: # seed the tree with the forced edge before sorting takes over
u, v, w = edges[forced]
if union(u, v):
weight += w
components -= 1
for i in order:
if i == skipped:
continue
u, v, w = edges[i]
if union(u, v):
weight += w
components -= 1
return weight if components == 1 else float("inf") # inf = no spanning tree
baseline = kruskal(-1, -1)
critical: list[int] = []
pseudo_critical: list[int] = []
for i in range(len(edges)):
if kruskal(i, -1) > baseline: # excluding it hurts (or disconnects): in EVERY MST
critical.append(i)
elif kruskal(-1, i) == baseline: # forcing it in stays optimal: in SOME MST
pseudo_critical.append(i)
return [critical, pseudo_critical]
// LC 1489. Compute the baseline MST weight with Kruskal, then re-run Kruskal
// twice per edge: once with the edge EXCLUDED (a higher weight or a
// disconnected result marks it critical) and once with it FORCED IN first
// (matching the baseline weight marks it pseudo-critical). Sorting edge
// indices once and sharing them across runs keeps each re-run cheap.
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>> edges) {
int m = static_cast<int>(edges.size());
vector<int> order(m);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return edges[a][2] < edges[b][2]; });
// Kruskal that can force one edge in first and skip another; returns the
// spanning weight, or -1 when the result is disconnected.
auto kruskal = [&](int skip, int force) -> long long {
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
auto find = [&](int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving
return x;
};
int components = n;
long long total = 0;
auto unite = [&](int a, int b) -> bool {
a = find(a);
b = find(b);
if (a == b) return false;
parent[a] = b;
--components;
return true;
};
if (force != -1 && unite(edges[force][0], edges[force][1])) total += edges[force][2];
for (int i : order) {
if (i == skip) continue;
if (unite(edges[i][0], edges[i][1])) total += edges[i][2];
}
return components == 1 ? total : -1;
};
long long base = kruskal(-1, -1);
vector<int> critical, pseudo;
for (int i = 0; i < m; ++i) {
long long without = kruskal(i, -1);
if (without == -1 || without > base) {
critical.push_back(i); // excluding it costs more or disconnects
} else if (kruskal(-1, i) == base) {
pseudo.push_back(i); // forcing it in still achieves the optimum
}
}
return {critical, pseudo};
}
/// LC 1489. Kruskal three ways: once for the baseline MST weight, then per
/// edge once with it excluded and once with it forced in first. Exclusion
/// raising the weight (or disconnecting the graph) marks the edge critical;
/// otherwise forcing it in while still matching the baseline marks it
/// pseudo-critical, since some MST can carry it.
pub fn find_critical_and_pseudo_critical_edges(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
fn find(parent: &mut [usize], x: usize) -> usize {
let mut root = x;
while parent[root] != root {
root = parent[root];
}
let mut cur = x;
while parent[cur] != root {
let next = parent[cur];
parent[cur] = root; // path compression
cur = next;
}
root
}
fn union(parent: &mut [usize], a: usize, b: usize) -> bool {
let (ra, rb) = (find(parent, a), find(parent, b));
if ra == rb {
return false;
}
parent[ra] = rb;
true
}
/// Kruskal over `order`, optionally skipping or force-including one edge.
/// Returns the spanning weight, or None when the result is disconnected.
fn mst(
n: usize,
edges: &[Vec<i32>],
order: &[usize],
skip: Option<usize>,
force: Option<usize>,
) -> Option<i32> {
let mut parent: Vec<usize> = (0..n).collect();
let mut weight = 0;
let mut used = 0;
if let Some(f) = force {
union(&mut parent, edges[f][0] as usize, edges[f][1] as usize);
weight += edges[f][2];
used += 1;
}
for &i in order {
if Some(i) == skip || Some(i) == force {
continue;
}
if union(&mut parent, edges[i][0] as usize, edges[i][1] as usize) {
weight += edges[i][2];
used += 1;
}
}
if used == n - 1 { Some(weight) } else { None }
}
let n = n as usize;
let mut order: Vec<usize> = (0..edges.len()).collect();
order.sort_by_key(|&i| edges[i][2]);
let base = mst(n, &edges, &order, None, None).unwrap();
let mut critical = Vec::new();
let mut pseudo = Vec::new();
for i in 0..edges.len() {
match mst(n, &edges, &order, Some(i), None) {
Some(w) if w == base => {
if mst(n, &edges, &order, None, Some(i)) == Some(base) {
pseudo.push(i as i32);
}
}
_ => critical.push(i as i32), // weight rose or graph fell apart
}
}
vec![critical, pseudo]
}
/** LC 1489. Kruskal baseline, then per edge: excluding it raises the weight => critical; forcing it keeps the weight => pseudo. */
export function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
const sorted = edges
.map((edge, index) => [edge[0], edge[1], edge[2], index]) // remember original positions before sorting
.sort((a, b) => a[2] - b[2]);
// Kruskal that can skip one edge and/or seed one edge first; Infinity marks a disconnected result
const mstWeight = (skip: number, force: number): number => {
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
};
const union = (a: number, b: number): boolean => {
const rootA = find(a);
const rootB = find(b);
if (rootA === rootB) return false;
parent[rootA] = rootB;
return true;
};
let weight = 0;
let used = 0;
if (force !== -1) {
const [u, v, w] = edges[force];
union(u, v);
weight += w;
used = 1;
}
for (const [u, v, w, index] of sorted) {
if (index === skip) continue;
if (union(u, v)) {
weight += w;
used++;
}
}
return used === n - 1 ? weight : Infinity;
};
const baseline = mstWeight(-1, -1);
const critical: number[] = [];
const pseudoCritical: number[] = [];
for (let i = 0; i < edges.length; i++) {
if (mstWeight(i, -1) > baseline) {
critical.push(i); // dropping it costs more (or disconnects): every MST needs it
} else if (mstWeight(-1, i) === baseline) {
pseudoCritical.push(i); // optional, but forcing it first still reaches the optimum
}
}
return [critical, pseudoCritical];
}
// LC 1489. Kruskal once for the baseline, then per edge: EXCLUDING it raises
// the weight (or disconnects) = critical; FORCING it in keeps the weight = pseudo.
func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {
m := len(edges)
order := make([]int, m) // edge indices sorted by weight, shared across runs
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return edges[order[a]][2] < edges[order[b]][2] })
// kruskal can force one edge in first and skip another; it returns the
// spanning weight, or -1 when the result is disconnected.
kruskal := func(skip, force int) int {
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
components := n
total := 0
unite := func(a, b int) bool {
a, b = find(a), find(b)
if a == b {
return false
}
parent[a] = b
components--
return true
}
if force != -1 && unite(edges[force][0], edges[force][1]) {
total += edges[force][2]
}
for _, i := range order {
if i == skip {
continue
}
if unite(edges[i][0], edges[i][1]) {
total += edges[i][2]
}
}
if components != 1 {
return -1 // no spanning tree
}
return total
}
base := kruskal(-1, -1)
critical, pseudo := []int{}, []int{}
for i := 0; i < m; i++ {
if without := kruskal(i, -1); without == -1 || without > base {
critical = append(critical, i) // excluding it costs more or disconnects
} else if kruskal(-1, i) == base {
pseudo = append(pseudo, i) // forcing it in still achieves the optimum
}
}
return [][]int{critical, pseudo}
}
// LC 1489. Kruskal once for the baseline, then twice per edge: EXCLUDED (weight
// rises or disconnects -> critical) and FORCED IN first (weight still matches
// -> pseudo-critical), sharing one sorted index order across runs.
func findCriticalAndPseudoCriticalEdges(_ n: Int, _ edges: [[Int]]) -> [[Int]] {
let m = edges.count
let order = (0..<m).sorted { edges[$0][2] < edges[$1][2] } // indices by weight
func kruskal(skip: Int, force: Int) -> Int { // spanning weight, or -1 if disconnected
var parent = Array(0..<n)
func find(_ x: Int) -> Int {
var x = x
while parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
var components = n
var total = 0
func unite(_ a: Int, _ b: Int) -> Bool {
let ra = find(a), rb = find(b)
if ra == rb { return false } // edge would close a cycle
parent[ra] = rb
components -= 1
return true
}
if force != -1 && unite(edges[force][0], edges[force][1]) { total += edges[force][2] }
for i in order {
if i == skip { continue }
if unite(edges[i][0], edges[i][1]) { total += edges[i][2] }
}
return components == 1 ? total : -1
}
let base = kruskal(skip: -1, force: -1)
var critical: [Int] = []
var pseudo: [Int] = []
for i in 0..<m {
let without = kruskal(skip: i, force: -1)
if without == -1 || without > base {
critical.append(i) // excluding it costs more or disconnects: in EVERY MST
} else if kruskal(skip: -1, force: i) == base {
pseudo.append(i) // forcing it in still achieves the optimum: in SOME MST
}
}
return [critical, pseudo]
}
9. Build a Matrix With Conditions
Hard · LC 2392
Build a k by k matrix containing 1 through k exactly once, where row conditions force one number above another and column conditions force one number left of another. Topologically sort the numbers twice, once over row conditions and once over column conditions, assigning each number a row index and a column index. The row and column axes never interact, which is the insight; a cycle in either sort means returning an empty matrix.
def build_matrix(k: int, row_conditions: list[list[int]], col_conditions: list[list[int]]) -> list[list[int]]:
"""LC 2392. Build a Matrix With Conditions.
The two axes never interact: a number's row index is decided purely
by row conditions and its column index purely by column conditions.
So run Kahn's topological sort twice -- once per axis -- and place
number x at (row position in the first order, column position in the
second). A cycle in either sort means no matrix exists. O(k^2 +
conditions) time, O(k^2) space for the output.
"""
def topo_order(conditions: list[list[int]]) -> "list[int] | None":
graph: list[list[int]] = [[] for _ in range(k + 1)] # 1-indexed numbers
indegree = [0] * (k + 1)
for above, below in conditions:
graph[above].append(below)
indegree[below] += 1 # duplicates are fine: pushed and drained in pairs
queue = deque(num for num in range(1, k + 1) if indegree[num] == 0)
order: list[int] = []
while queue:
num = queue.popleft()
order.append(num)
for nxt in graph[num]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == k else None # short order = cycle
row_order = topo_order(row_conditions)
col_order = topo_order(col_conditions)
if row_order is None or col_order is None:
return []
row_of = {num: r for r, num in enumerate(row_order)}
col_of = {num: c for c, num in enumerate(col_order)}
matrix = [[0] * k for _ in range(k)]
for num in range(1, k + 1):
matrix[row_of[num]][col_of[num]] = num # the axes place it independently
return matrix
// LC 2392. The row and column axes never interact, which is the insight: run
// Kahn's topological sort twice, once over the row conditions and once over
// the column conditions, assigning each number a row index and a column index
// independently. A cycle in either sort means no matrix exists; otherwise
// place value v at (rowPos[v], colPos[v]) and zero-fill the rest.
vector<vector<int>> buildMatrix(int k, vector<vector<int>> rowConditions,
vector<vector<int>> colConditions) {
auto topo = [&](const vector<vector<int>>& conditions) -> vector<int> {
vector<vector<int>> adj(k + 1);
vector<int> indeg(k + 1, 0);
for (const auto& cond : conditions) {
adj[cond[0]].push_back(cond[1]);
++indeg[cond[1]];
}
queue<int> q;
for (int v = 1; v <= k; ++v)
if (indeg[v] == 0) q.push(v);
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u])
if (--indeg[v] == 0) q.push(v);
}
if (static_cast<int>(order.size()) != k) order.clear(); // cycle
return order;
};
vector<int> rowOrder = topo(rowConditions);
vector<int> colOrder = topo(colConditions);
if (rowOrder.empty() || colOrder.empty()) return {};
vector<int> rowPos(k + 1), colPos(k + 1);
for (int i = 0; i < k; ++i) {
rowPos[rowOrder[i]] = i;
colPos[colOrder[i]] = i;
}
vector<vector<int>> mat(k, vector<int>(k, 0));
for (int v = 1; v <= k; ++v) mat[rowPos[v]][colPos[v]] = v;
return mat;
}
/// LC 2392. The row and column axes never interact: topologically sort the
/// numbers once over the row conditions and once over the column conditions,
/// giving each number an independent row index and column index, then place
/// number v at (row_pos[v], col_pos[v]). A cycle in either Kahn pass means an
/// empty matrix.
pub fn build_matrix(
k: i32,
row_conditions: Vec<Vec<i32>>,
col_conditions: Vec<Vec<i32>>,
) -> Vec<Vec<i32>> {
/// Kahn's BFS over numbers 1..=k; pos[v] is v's topological slot.
fn topo_positions(k: usize, conditions: &[Vec<i32>]) -> Option<Vec<usize>> {
let mut adj = vec![Vec::new(); k + 1];
let mut indegree = vec![0usize; k + 1];
for c in conditions {
adj[c[0] as usize].push(c[1] as usize);
indegree[c[1] as usize] += 1; // duplicate edges count twice: fine
}
let mut queue: VecDeque<usize> = (1..=k).filter(|&v| indegree[v] == 0).collect();
let mut pos = vec![0usize; k + 1];
let mut count = 0;
while let Some(u) = queue.pop_front() {
pos[u] = count;
count += 1;
for &v in &adj[u] {
indegree[v] -= 1;
if indegree[v] == 0 {
queue.push_back(v);
}
}
}
if count == k { Some(pos) } else { None } // leftover numbers = cycle
}
let k = k as usize;
let (row_pos, col_pos) =
match (topo_positions(k, &row_conditions), topo_positions(k, &col_conditions)) {
(Some(r), Some(c)) => (r, c),
_ => return Vec::new(),
};
let mut matrix = vec![vec![0; k]; k];
for v in 1..=k {
matrix[row_pos[v]][col_pos[v]] = v as i32;
}
matrix
}
/** LC 2392. Row and column axes never interact: topo-sort each condition set separately, then place by (rowOf, colOf). */
export function buildMatrix(k: number, rowConditions: number[][], colConditions: number[][]): number[][] {
const topoSort = (conditions: number[][]): number[] | null => {
const next: number[][] = Array.from({ length: k + 1 }, () => []);
const indegree = new Array<number>(k + 1).fill(0);
for (const [before, after] of conditions) {
next[before].push(after); // duplicate conditions add parallel edges; Kahn handles them fine
indegree[after]++;
}
const queue: number[] = [];
for (let value = 1; value <= k; value++) {
if (indegree[value] === 0) queue.push(value);
}
const order: number[] = [];
for (let head = 0; head < queue.length; head++) {
const value = queue[head];
order.push(value);
for (const after of next[value]) {
if (--indegree[after] === 0) queue.push(after);
}
}
return order.length === k ? order : null; // missing values mean a cycle
};
const rowOrder = topoSort(rowConditions);
const colOrder = topoSort(colConditions);
if (rowOrder === null || colOrder === null) return [];
const rowOf = new Array<number>(k + 1);
const colOf = new Array<number>(k + 1);
rowOrder.forEach((value, index) => (rowOf[value] = index));
colOrder.forEach((value, index) => (colOf[value] = index));
const matrix = Array.from({ length: k }, () => new Array<number>(k).fill(0));
for (let value = 1; value <= k; value++) matrix[rowOf[value]][colOf[value]] = value; // axes assigned independently
return matrix;
}
// LC 2392. The row and column axes never interact: two Kahn topo sorts, one
// per axis, place number v at (rowPos[v], colPos[v]); a cycle in either means no matrix.
func buildMatrix(k int, rowConditions [][]int, colConditions [][]int) [][]int {
topo := func(conditions [][]int) []int {
adj := make([][]int, k+1) // 1-indexed numbers
indeg := make([]int, k+1)
for _, cond := range conditions {
adj[cond[0]] = append(adj[cond[0]], cond[1])
indeg[cond[1]]++
}
queue := []int{}
for v := 1; v <= k; v++ {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
order := []int{}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
order = append(order, u)
for _, v := range adj[u] {
indeg[v]--
if indeg[v] == 0 {
queue = append(queue, v)
}
}
}
if len(order) != k {
return nil // short order = cycle
}
return order
}
rowOrder := topo(rowConditions)
colOrder := topo(colConditions)
if rowOrder == nil || colOrder == nil {
return [][]int{}
}
rowPos := make([]int, k+1)
colPos := make([]int, k+1)
for i := 0; i < k; i++ {
rowPos[rowOrder[i]] = i
colPos[colOrder[i]] = i
}
mat := make([][]int, k)
for r := range mat {
mat[r] = make([]int, k)
}
for v := 1; v <= k; v++ {
mat[rowPos[v]][colPos[v]] = v // the axes place it independently
}
return mat
}
// LC 2392. The axes never interact: one Kahn topo sort per axis fixes each
// number's row and column independently; a cycle in either means no matrix.
func buildMatrix(_ k: Int, _ rowConditions: [[Int]], _ colConditions: [[Int]]) -> [[Int]] {
func topo(_ conditions: [[Int]]) -> [Int] {
var adj = [[Int]](repeating: [], count: k + 1) // 1-indexed numbers
var indeg = [Int](repeating: 0, count: k + 1)
for cond in conditions {
adj[cond[0]].append(cond[1])
indeg[cond[1]] += 1
}
var queue: [Int] = []
for v in 1...k where indeg[v] == 0 { queue.append(v) }
var head = 0
var order: [Int] = []
while head < queue.count {
let u = queue[head]
head += 1
order.append(u)
for v in adj[u] {
indeg[v] -= 1
if indeg[v] == 0 { queue.append(v) }
}
}
return order.count == k ? order : [] // short order = cycle
}
let rowOrder = topo(rowConditions)
let colOrder = topo(colConditions)
if rowOrder.isEmpty || colOrder.isEmpty { return [] }
var rowPos = [Int](repeating: 0, count: k + 1)
var colPos = [Int](repeating: 0, count: k + 1)
for i in 0..<k {
rowPos[rowOrder[i]] = i
colPos[colOrder[i]] = i
}
var mat = [[Int]](repeating: [Int](repeating: 0, count: k), count: k)
for v in 1...k { mat[rowPos[v]][colPos[v]] = v } // the axes place it independently
return mat
}
10. Greatest Common Divisor Traversal
Hard · LC 2709
Given an array of integers, decide whether every pair of indices connects through a path where adjacent elements share a gcd above 1. Factor each number and union it with a node representing each of its prime factors, then check that all numbers end up in one component. Routing unions through shared primes avoids comparing all pairs; a single element is trivially true, while any 1 in a longer array forces false.
def can_traverse_all_pairs(nums: list[int]) -> bool:
"""LC 2709. Greatest Common Divisor Traversal.
Indices connect when their values share a prime factor, so instead
of testing all pairs, union each index with a HUB node per prime
factor of its value: two numbers sharing a prime land in the same
component through that prime's hub. A smallest-prime-factor sieve
factors every value in O(log value). Special cases: one element is
trivially true (no pairs to connect), and any 1 in a longer array is
false since gcd(1, anything) is 1. O(max(nums) log log max(nums) +
n log max(nums)) time, O(max(nums) + n) space.
"""
n = len(nums)
if n == 1:
return True # a single element has no pairs to connect
if 1 in nums:
return False # a 1 shares gcd 1 with everything: it can never join
limit = max(nums)
smallest_prime = list(range(limit + 1)) # spf sieve: spf[x] = smallest prime of x
for p in range(2, int(limit ** 0.5) + 1):
if smallest_prime[p] == p: # p itself is prime
for multiple in range(p * p, limit + 1, p):
if smallest_prime[multiple] == multiple: # first prime to touch it wins
smallest_prime[multiple] = p
# nodes 0..n-1 are the indices; node n + p is prime p's hub
parent = list(range(n + limit + 1))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(a: int, b: int) -> None:
root_a, root_b = find(a), find(b)
if root_a != root_b:
parent[root_a] = root_b
for i, value in enumerate(nums):
while value > 1: # peel primes via the sieve: O(log value) factors
p = smallest_prime[value]
union(i, n + p) # join the index to its prime's hub
while value % p == 0:
value //= p
everyone = find(0)
return all(find(i) == everyone for i in range(1, n))
// LC 2709. Union-find routed through shared prime factors instead of all
// pairs: a smallest-prime-factor sieve factors each number in O(log x), and
// each prime unions the current index with the first index that carried it.
// Everything must land in one component; a single element is trivially true,
// while any 1 in a longer array is isolated (no prime factors) and forces
// false.
bool canTraverseAllPairs(vector<int> nums) {
int n = static_cast<int>(nums.size());
if (n == 1) return true; // no pairs to connect
int mx = 0;
for (int x : nums) {
if (x == 1) return false; // 1 has no prime factors: isolated node
mx = max(mx, x);
}
vector<int> spf(mx + 1, 0); // smallest prime factor sieve
for (int i = 2; i <= mx; ++i)
if (spf[i] == 0)
for (long long j = i; j <= mx; j += i)
if (spf[j] == 0) spf[j] = i;
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
auto find = [&](int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving
return x;
};
unordered_map<int, int> firstIndex; // prime -> first index containing it
for (int i = 0; i < n; ++i) {
int x = nums[i];
while (x > 1) {
int p = spf[x];
while (x % p == 0) x /= p;
auto it = firstIndex.find(p);
if (it == firstIndex.end())
firstIndex[p] = i;
else
parent[find(i)] = find(it->second);
}
}
for (int i = 1; i < n; ++i)
if (find(i) != find(0)) return false;
return true;
}
/// LC 2709. Union-find routed through prime factors instead of all pairs:
/// a smallest-prime-factor sieve factors each number in O(log value), and
/// each index unions with the first index that owned each of its primes.
/// All indices in one component means every pair connects. A single element
/// (even [1]) is trivially true, while any 1 in a longer array is false
/// because 1 has no prime factors to travel through.
pub fn can_traverse_all_pairs(nums: Vec<i32>) -> bool {
fn find(parent: &mut [usize], x: usize) -> usize {
let mut root = x;
while parent[root] != root {
root = parent[root];
}
let mut cur = x;
while parent[cur] != root {
let next = parent[cur];
parent[cur] = root; // path compression
cur = next;
}
root
}
fn union(parent: &mut [usize], a: usize, b: usize) {
let (ra, rb) = (find(parent, a), find(parent, b));
if ra != rb {
parent[ra] = rb;
}
}
let n = nums.len();
if n == 1 {
return true;
}
if nums.iter().any(|&x| x == 1) {
return false;
}
let max = *nums.iter().max().unwrap() as usize;
let mut spf: Vec<usize> = (0..=max).collect(); // smallest prime factor
let mut i = 2;
while i * i <= max {
if spf[i] == i {
let mut j = i * i;
while j <= max {
if spf[j] == j {
spf[j] = i;
}
j += i;
}
}
i += 1;
}
let mut parent: Vec<usize> = (0..n).collect();
let mut owner: HashMap<usize, usize> = HashMap::new(); // prime -> index
for (idx, &num) in nums.iter().enumerate() {
let mut x = num as usize;
while x > 1 {
let p = spf[x];
let first = *owner.entry(p).or_insert(idx);
if first != idx {
union(&mut parent, idx, first);
}
while x % p == 0 {
x /= p;
}
}
}
let root = find(&mut parent, 0);
(1..n).all(|i| find(&mut parent, i) == root)
}
/** LC 2709. Union each index with its prime factors (via an SPF sieve) instead of comparing all pairs. */
export function canTraverseAllPairs(nums: number[]): boolean {
const n = nums.length;
if (n === 1) return true; // no pair to connect
if (nums.includes(1)) return false; // 1 shares no prime with anything, so it strands
const max = Math.max(...nums);
const spf = new Array<number>(max + 1).fill(0); // smallest prime factor of each value
for (let i = 2; i <= max; i++) {
if (spf[i] === 0) {
for (let j = i; j <= max; j += i) {
if (spf[j] === 0) spf[j] = i;
}
}
}
const parent = Array.from({ length: n }, (_, i) => i); // indices first; prime nodes appended on demand
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
};
const union = (a: number, b: number): void => {
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) parent[rootA] = rootB;
};
const nodeOfPrime = new Map<number, number>();
for (let i = 0; i < n; i++) {
let value = nums[i];
while (value > 1) {
const prime = spf[value];
let node = nodeOfPrime.get(prime);
if (node === undefined) {
node = parent.length;
parent.push(node);
nodeOfPrime.set(prime, node);
}
union(i, node); // shared primes route the connection, avoiding O(n^2) pair checks
while (value % prime === 0) value /= prime;
}
}
const root = find(0);
for (let i = 1; i < n; i++) {
if (find(i) !== root) return false;
}
return true;
}
// LC 2709. Union indices through shared prime factors (spf sieve) instead of
// all pairs; everything must land in one component. A lone element is true, any 1 is false.
func canTraverseAllPairs(nums []int) bool {
n := len(nums)
if n == 1 {
return true // no pairs to connect
}
mx := 0
for _, x := range nums {
if x == 1 {
return false // 1 has no prime factors: isolated node
}
if x > mx {
mx = x
}
}
spf := make([]int, mx+1) // smallest prime factor sieve
for i := 2; i <= mx; i++ {
if spf[i] == 0 {
for j := i; j <= mx; j += i {
if spf[j] == 0 {
spf[j] = i
}
}
}
}
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
firstIndex := map[int]int{} // prime -> first index containing it
for i, x := range nums {
for x > 1 { // peel primes via the sieve
p := spf[x]
for x%p == 0 {
x /= p
}
if j, ok := firstIndex[p]; ok {
parent[find(i)] = find(j) // join through the prime's hub index
} else {
firstIndex[p] = i
}
}
}
for i := 1; i < n; i++ {
if find(i) != find(0) {
return false
}
}
return true
}
// LC 2709. Union indices through shared prime factors (spf sieve factors each
// value in O(log x)); everything must land in one component. A lone element is
// trivially true; any 1 in a longer array is isolated and forces false.
func canTraverseAllPairs(_ nums: [Int]) -> Bool {
let n = nums.count
if n == 1 { return true } // no pairs to connect
var mx = 0
for x in nums {
if x == 1 { return false } // 1 has no prime factors: isolated node
mx = max(mx, x)
}
var spf = [Int](repeating: 0, count: mx + 1) // smallest prime factor sieve
for i in 2...mx where spf[i] == 0 {
var j = i
while j <= mx {
if spf[j] == 0 { spf[j] = i }
j += i
}
}
var parent = Array(0..<n)
func find(_ x: Int) -> Int {
var x = x
while parent[x] != x {
parent[x] = parent[parent[x]] // path halving
x = parent[x]
}
return x
}
var firstIndex: [Int: Int] = [:] // prime -> first index containing it
for (i, value) in nums.enumerated() {
var x = value
while x > 1 {
let p = spf[x]
while x % p == 0 { x /= p }
if let first = firstIndex[p] {
parent[find(i)] = find(first) // join through the prime's first carrier
} else {
firstIndex[p] = i
}
}
}
for i in 1..<n where find(i) != find(0) { return false }
return true
}