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.
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some servers unable to reach some other server.
Return all critical connections in the network in any order.
Example 1:
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted.
Example 2:
Input: n = 2, connections = [[0,1]] Output: [[0,1]]
Constraints:
2 <= n <= 105n - 1 <= connections.length <= 1050 <= ai, bi <= n - 1ai != biProblem summary: There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network. A critical connection is a connection that, if removed, will make some servers unable to reach some other server. Return all critical connections in the network in any order.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: General problem-solving
4 [[0,1],[1,2],[2,0],[1,3]]
2 [[0,1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1192: Critical Connections in a Network
class Solution {
private int now;
private List<Integer>[] g;
private List<List<Integer>> ans = new ArrayList<>();
private int[] dfn;
private int[] low;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
dfn = new int[n];
low = new int[n];
for (var e : connections) {
int a = e.get(0), b = e.get(1);
g[a].add(b);
g[b].add(a);
}
tarjan(0, -1);
return ans;
}
private void tarjan(int a, int fa) {
dfn[a] = low[a] = ++now;
for (int b : g[a]) {
if (b == fa) {
continue;
}
if (dfn[b] == 0) {
tarjan(b, a);
low[a] = Math.min(low[a], low[b]);
if (low[b] > dfn[a]) {
ans.add(List.of(a, b));
}
} else {
low[a] = Math.min(low[a], dfn[b]);
}
}
}
}
// Accepted solution for LeetCode #1192: Critical Connections in a Network
func criticalConnections(n int, connections [][]int) (ans [][]int) {
now := 0
g := make([][]int, n)
dfn := make([]int, n)
low := make([]int, n)
for _, e := range connections {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
var tarjan func(int, int)
tarjan = func(a, fa int) {
now++
dfn[a], low[a] = now, now
for _, b := range g[a] {
if b == fa {
continue
}
if dfn[b] == 0 {
tarjan(b, a)
low[a] = min(low[a], low[b])
if low[b] > dfn[a] {
ans = append(ans, []int{a, b})
}
} else {
low[a] = min(low[a], dfn[b])
}
}
}
tarjan(0, -1)
return
}
# Accepted solution for LeetCode #1192: Critical Connections in a Network
class Solution:
def criticalConnections(
self, n: int, connections: List[List[int]]
) -> List[List[int]]:
def tarjan(a: int, fa: int):
nonlocal now
now += 1
dfn[a] = low[a] = now
for b in g[a]:
if b == fa:
continue
if not dfn[b]:
tarjan(b, a)
low[a] = min(low[a], low[b])
if low[b] > dfn[a]:
ans.append([a, b])
else:
low[a] = min(low[a], dfn[b])
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append(b)
g[b].append(a)
dfn = [0] * n
low = [0] * n
now = 0
ans = []
tarjan(0, -1)
return ans
// Accepted solution for LeetCode #1192: Critical Connections in a Network
struct Solution;
#[derive(Debug, Eq, PartialEq, Clone)]
struct Node {
id: usize,
discovery: usize,
lowest: usize,
on_stack: bool,
}
impl Node {
fn new(id: usize) -> Node {
let discovery = std::usize::MAX;
let lowest = std::usize::MAX;
let on_stack = false;
Node {
id,
discovery,
lowest,
on_stack,
}
}
}
impl Solution {
fn critical_connections(n: i32, connections: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = n as usize;
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
for connection in connections {
let u = connection[0] as usize;
let v = connection[1] as usize;
graph[u].push(v);
graph[v].push(u);
}
let mut time = 0;
let mut nodes: Vec<Node> = (0..n).map(Node::new).collect();
let mut res = vec![];
Self::dfs(0, 0, &mut time, &mut nodes, &mut res, &graph);
res
}
fn dfs(
u: usize,
parent: usize,
time: &mut usize,
nodes: &mut Vec<Node>,
edges: &mut Vec<Vec<i32>>,
graph: &[Vec<usize>],
) {
nodes[u].discovery = *time;
nodes[u].lowest = *time;
*time += 1;
for &v in &graph[u] {
if v == parent {
continue;
}
if nodes[v].discovery == std::usize::MAX {
Self::dfs(v, u, time, nodes, edges, graph);
nodes[u].lowest = nodes[u].lowest.min(nodes[v].lowest);
if nodes[v].lowest > nodes[u].discovery {
edges.push(vec![u as i32, v as i32]);
}
} else {
nodes[u].lowest = nodes[u].lowest.min(nodes[v].discovery);
}
}
}
}
#[test]
fn test() {
let n = 4;
let connections = vec_vec_i32![[0, 1], [1, 2], [2, 0], [1, 3]];
let res = vec_vec_i32![[1, 3]];
assert_eq!(Solution::critical_connections(n, connections), res);
let n = 5;
let connections = vec_vec_i32![[1, 0], [2, 0], [3, 0], [4, 1], [4, 2], [4, 0]];
let res = vec_vec_i32![[0, 3]];
assert_eq!(Solution::critical_connections(n, connections), res);
}
// Accepted solution for LeetCode #1192: Critical Connections in a Network
function criticalConnections(n: number, connections: number[][]): number[][] {
let now: number = 0;
const g: number[][] = Array(n)
.fill(0)
.map(() => []);
const dfn: number[] = Array(n).fill(0);
const low: number[] = Array(n).fill(0);
for (const [a, b] of connections) {
g[a].push(b);
g[b].push(a);
}
const ans: number[][] = [];
const tarjan = (a: number, fa: number) => {
dfn[a] = low[a] = ++now;
for (const b of g[a]) {
if (b === fa) {
continue;
}
if (!dfn[b]) {
tarjan(b, a);
low[a] = Math.min(low[a], low[b]);
if (low[b] > dfn[a]) {
ans.push([a, b]);
}
} else {
low[a] = Math.min(low[a], dfn[b]);
}
}
};
tarjan(0, -1);
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
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.