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.
Move from brute-force thinking to an efficient approach using union-find strategy.
There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.
You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.
Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.
Example 1:
Input: n = 4, connections = [[0,1],[0,2],[1,2]] Output: 1 Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.
Example 2:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] Output: 2
Example 3:
Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] Output: -1 Explanation: There are not enough cables.
Constraints:
1 <= n <= 1051 <= connections.length <= min(n * (n - 1) / 2, 105)connections[i].length == 20 <= ai, bi < nai != biProblem summary: There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network. You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Union-Find
4 [[0,1],[0,2],[1,2]]
6 [[0,1],[0,2],[0,3],[1,2],[1,3]]
6 [[0,1],[0,2],[0,3],[1,2]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1319: Number of Operations to Make Network Connected
class Solution {
private int[] p;
public int makeConnected(int n, int[][] connections) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
int cnt = 0;
for (int[] e : connections) {
int pa = find(e[0]), pb = find(e[1]);
if (pa == pb) {
++cnt;
} else {
p[pa] = pb;
--n;
}
}
return n - 1 > cnt ? -1 : n - 1;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
// Accepted solution for LeetCode #1319: Number of Operations to Make Network Connected
func makeConnected(n int, connections [][]int) int {
p := make([]int, n)
for i := range p {
p[i] = i
}
cnt := 0
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range connections {
pa, pb := find(e[0]), find(e[1])
if pa == pb {
cnt++
} else {
p[pa] = pb
n--
}
}
if n-1 > cnt {
return -1
}
return n - 1
}
# Accepted solution for LeetCode #1319: Number of Operations to Make Network Connected
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
cnt = 0
p = list(range(n))
for a, b in connections:
pa, pb = find(a), find(b)
if pa == pb:
cnt += 1
else:
p[pa] = pb
n -= 1
return -1 if n - 1 > cnt else n - 1
// Accepted solution for LeetCode #1319: Number of Operations to Make Network Connected
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) {
let i = self.find(i);
let j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
}
}
}
impl Solution {
fn make_connected(n: i32, connections: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let m = connections.len();
if m + 1 < n {
return -1;
}
let mut uf = UnionFind::new(n);
for connection in connections {
let i = connection[0] as usize;
let j = connection[1] as usize;
uf.union(i, j);
}
(uf.n - 1) as i32
}
}
#[test]
fn test() {
let n = 4;
let connections = vec_vec_i32![[0, 1], [0, 2], [1, 2]];
let res = 1;
assert_eq!(Solution::make_connected(n, connections), res);
let n = 6;
let connections = vec_vec_i32![[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]];
let res = 2;
assert_eq!(Solution::make_connected(n, connections), res);
let n = 6;
let connections = vec_vec_i32![[0, 1], [0, 2], [0, 3], [1, 2]];
let res = -1;
assert_eq!(Solution::make_connected(n, connections), res);
let n = 5;
let connections = vec_vec_i32![[0, 1], [0, 2], [3, 4], [2, 3]];
let res = 0;
assert_eq!(Solution::make_connected(n, connections), res);
}
// Accepted solution for LeetCode #1319: Number of Operations to Make Network Connected
function makeConnected(n: number, connections: number[][]): number {
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
let cnt = 0;
for (const [a, b] of connections) {
const [pa, pb] = [find(a), find(b)];
if (pa === pb) {
++cnt;
} else {
p[pa] = pb;
--n;
}
}
return cnt >= n - 1 ? n - 1 : -1;
}
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.