Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Example 1:
Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]] Output: [[0,1],[2,3,4,5]] Explanation: The figure above describes the graph. The following figure shows all the possible MSTs: Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output. The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2:
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]] Output: [[],[0,1,2,3]] Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints:
2 <= n <= 1001 <= edges.length <= min(200, n * (n - 1) / 2)edges[i].length == 30 <= ai < bi < n1 <= weighti <= 1000(ai, bi) are distinct.Problem summary: Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight. Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all. Note that you can return the indices of the edges in any order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Union-Find
5 [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
4 [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
class Solution {
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
for (int i = 0; i < edges.length; ++i) {
int[] e = edges[i];
int[] t = new int[4];
System.arraycopy(e, 0, t, 0, 3);
t[3] = i;
edges[i] = t;
}
Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
int v = 0;
UnionFind uf = new UnionFind(n);
for (int[] e : edges) {
int f = e[0], t = e[1], w = e[2];
if (uf.union(f, t)) {
v += w;
}
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < 2; ++i) {
ans.add(new ArrayList<>());
}
for (int[] e : edges) {
int f = e[0], t = e[1], w = e[2], i = e[3];
uf = new UnionFind(n);
int k = 0;
for (int[] ne : edges) {
int x = ne[0], y = ne[1], z = ne[2], j = ne[3];
if (j != i && uf.union(x, y)) {
k += z;
}
}
if (uf.getN() > 1 || (uf.getN() == 1 && k > v)) {
ans.get(0).add(i);
continue;
}
uf = new UnionFind(n);
uf.union(f, t);
k = w;
for (int[] ne : edges) {
int x = ne[0], y = ne[1], z = ne[2], j = ne[3];
if (j != i && uf.union(x, y)) {
k += z;
}
}
if (k == v) {
ans.get(1).add(i);
}
}
return ans;
}
}
class UnionFind {
private int[] p;
private int n;
public UnionFind(int n) {
p = new int[n];
this.n = n;
for (int i = 0; i < n; ++i) {
p[i] = i;
}
}
public int getN() {
return n;
}
public boolean union(int a, int b) {
if (find(a) == find(b)) {
return false;
}
p[find(a)] = find(b);
--n;
return true;
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
// Accepted solution for LeetCode #1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
type unionFind struct {
p []int
n int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
for i := range p {
p[i] = i
}
return &unionFind{p, n}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
if uf.find(a) == uf.find(b) {
return false
}
uf.p[uf.find(a)] = uf.find(b)
uf.n--
return true
}
func findCriticalAndPseudoCriticalEdges(n int, edges [][]int) [][]int {
for i := range edges {
edges[i] = append(edges[i], i)
}
sort.Slice(edges, func(i, j int) bool {
return edges[i][2] < edges[j][2]
})
v := 0
uf := newUnionFind(n)
for _, e := range edges {
f, t, w := e[0], e[1], e[2]
if uf.union(f, t) {
v += w
}
}
ans := make([][]int, 2)
for _, e := range edges {
f, t, w, i := e[0], e[1], e[2], e[3]
uf = newUnionFind(n)
k := 0
for _, ne := range edges {
x, y, z, j := ne[0], ne[1], ne[2], ne[3]
if j != i && uf.union(x, y) {
k += z
}
}
if uf.n > 1 || (uf.n == 1 && k > v) {
ans[0] = append(ans[0], i)
continue
}
uf = newUnionFind(n)
uf.union(f, t)
k = w
for _, ne := range edges {
x, y, z, j := ne[0], ne[1], ne[2], ne[3]
if j != i && uf.union(x, y) {
k += z
}
}
if k == v {
ans[1] = append(ans[1], i)
}
}
return ans
}
# Accepted solution for LeetCode #1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.n = n
def union(self, a, b):
if self.find(a) == self.find(b):
return False
self.p[self.find(a)] = self.find(b)
self.n -= 1
return True
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
class Solution:
def findCriticalAndPseudoCriticalEdges(
self, n: int, edges: List[List[int]]
) -> List[List[int]]:
for i, e in enumerate(edges):
e.append(i)
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
v = sum(w for f, t, w, _ in edges if uf.union(f, t))
ans = [[], []]
for f, t, w, i in edges:
uf = UnionFind(n)
k = sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if uf.n > 1 or (uf.n == 1 and k > v):
ans[0].append(i)
continue
uf = UnionFind(n)
uf.union(f, t)
k = w + sum(z for x, y, z, j in edges if j != i and uf.union(x, y))
if k == v:
ans[1].append(i)
return ans
// Accepted solution for LeetCode #1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
struct Solution;
struct UnionFind {
parent: Vec<usize>,
n: usize,
}
impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
i
} else {
let k = self.find(j);
self.parent[i] = k;
k
}
}
fn union(&mut self, i: usize, j: usize) -> bool {
let i = self.find(i);
let j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
true
} else {
false
}
}
}
impl Solution {
fn find_critical_and_pseudo_critical_edges(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let m = edges.len();
let n = n as usize;
let mut sorted_index: Vec<usize> = (0..m).collect();
sorted_index.sort_unstable_by_key(|&i| edges[i][2]);
let min_cost = Self::mst(std::usize::MAX, std::usize::MAX, &sorted_index, &edges, n);
let mut critical = vec![];
let mut noncritical = vec![];
for i in 0..m {
if Self::mst(i, std::usize::MAX, &sorted_index, &edges, n) > min_cost {
critical.push(i as i32);
} else {
if Self::mst(std::usize::MAX, i, &sorted_index, &edges, n) == min_cost {
noncritical.push(i as i32);
}
}
}
vec![critical, noncritical]
}
fn mst(skip: usize, pick: usize, sorted_index: &[usize], edges: &[Vec<i32>], n: usize) -> i32 {
let mut uf = UnionFind::new(n);
let mut res = 0;
if pick != std::usize::MAX {
if uf.union(edges[pick][0] as usize, edges[pick][1] as usize) {
res += edges[pick][2];
}
}
for &idx in sorted_index {
if idx != skip {
if uf.union(edges[idx][0] as usize, edges[idx][1] as usize) {
res += edges[idx][2];
}
}
}
if uf.n == 1 {
res
} else {
std::i32::MAX
}
}
}
#[test]
fn test() {
let n = 5;
let edges = vec_vec_i32![
[0, 1, 1],
[1, 2, 1],
[2, 3, 2],
[0, 3, 2],
[0, 4, 3],
[3, 4, 3],
[1, 4, 6]
];
let res = vec_vec_i32![[0, 1], [2, 3, 4, 5]];
assert_eq!(
Solution::find_critical_and_pseudo_critical_edges(n, edges),
res
);
let n = 4;
let edges = vec_vec_i32![[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 1]];
let res = vec_vec_i32![[], [0, 1, 2, 3]];
assert_eq!(
Solution::find_critical_and_pseudo_critical_edges(n, edges),
res
);
}
// Accepted solution for LeetCode #1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
type Edge = [number, number, number];
class UnionFind {
parents: number[];
ranks: number[];
constructor(n: number) {
this.parents = Array.from({ length: n }, (_, i) => i);
this.ranks = Array.from({ length: n }, () => 0);
}
find(node: number) {
let current = this.parents[node];
while (current !== this.parents[current]) {
this.parents[current] = this.parents[this.parents[current]];
current = this.parents[current];
}
return current;
}
union(a: number, b: number) {
const pa = this.find(a);
const pb = this.find(b);
if (pa === pb) return false;
if (this.ranks[pa] > this.ranks[pb]) {
this.parents[pb] = pa;
} else if (this.ranks[pa] < this.ranks[pb]) {
this.parents[pa] = pb;
} else {
this.parents[pb] = pa;
this.ranks[pa]++;
}
return true;
}
}
function findMST(
n: number,
edges: Edge[],
heap: typeof MinPriorityQueue,
): { edges: Edge[]; sum: number } {
const unionFind = new UnionFind(n);
const resultingEdges = [];
let sum = 0;
if (!heap.isEmpty()) {
const { element: minEdge } = heap.dequeue();
unionFind.union(minEdge[0], minEdge[1]);
resultingEdges.push(minEdge);
sum += minEdge[2];
}
for (let edge of edges) {
heap.enqueue(edge);
}
while (!heap.isEmpty() && resultingEdges.length < n - 1) {
const { element: minEdge } = heap.dequeue();
const isUnion = unionFind.union(minEdge[0], minEdge[1]);
if (!isUnion) continue;
resultingEdges.push(minEdge);
sum += minEdge[2];
}
if (resultingEdges.length < n - 1) return { sum: Infinity, edges: [] };
return { edges: resultingEdges, sum };
}
function buildHeap() {
return new MinPriorityQueue({ priority: (edge) => edge[2] });
}
function findCriticalAndPseudoCriticalEdges(
n: number,
edges: Edge[],
): number[][] {
const generalMST = findMST(n, edges, buildHeap());
const criticalEdges = [];
for (let edgeToExclude of generalMST.edges) {
const newEdges = edges.filter(
(edge) => edge.join(',') !== edgeToExclude.join(','),
);
const mst = findMST(n, newEdges, buildHeap());
if (mst.sum > generalMST.sum) {
criticalEdges.push(edgeToExclude);
}
}
const pseudoCriticalEdges = [];
for (let edge of edges) {
if (criticalEdges.map((e) => e.join(',')).includes(edge.join(',')))
continue;
const newEdges = edges.filter(
(possibleEdge) => possibleEdge.join(',') !== edge.join(','),
);
const heap = buildHeap();
heap.enqueue(edge);
const mst = findMST(n, newEdges, heap);
if (mst.sum === generalMST.sum) {
pseudoCriticalEdges.push(edge);
}
}
return [
criticalEdges.map((criticalEdge) =>
edges.findIndex(
(edge) => edge.join(',') === criticalEdge.join(','),
),
),
pseudoCriticalEdges.map((pCriticalEdge) =>
edges.findIndex(
(edge) => edge.join(',') === pCriticalEdge.join(','),
),
),
];
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.