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 array strategy.
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Example 1:
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]] Output: 18
Constraints:
1 <= points.length <= 1000-106 <= xi, yi <= 106(xi, yi) are distinct.Problem summary: You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Union-Find
[[0,0],[2,2],[3,10],[5,2],[7,0]]
[[3,12],[-2,5],[-4,1]]
minimum-number-of-lines-to-cover-points)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1584: Min Cost to Connect All Points
class Solution {
public int minCostConnectPoints(int[][] points) {
final int inf = 1 << 30;
int n = points.length;
int[][] g = new int[n][n];
for (int i = 0; i < n; ++i) {
int x1 = points[i][0], y1 = points[i][1];
for (int j = i + 1; j < n; ++j) {
int x2 = points[j][0], y2 = points[j][1];
int t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
g[i][j] = t;
g[j][i] = t;
}
}
int[] dist = new int[n];
boolean[] vis = new boolean[n];
Arrays.fill(dist, inf);
dist[0] = 0;
int ans = 0;
for (int i = 0; i < n; ++i) {
int j = -1;
for (int k = 0; k < n; ++k) {
if (!vis[k] && (j == -1 || dist[k] < dist[j])) {
j = k;
}
}
vis[j] = true;
ans += dist[j];
for (int k = 0; k < n; ++k) {
if (!vis[k]) {
dist[k] = Math.min(dist[k], g[j][k]);
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #1584: Min Cost to Connect All Points
func minCostConnectPoints(points [][]int) (ans int) {
n := len(points)
g := make([][]int, n)
vis := make([]bool, n)
dist := make([]int, n)
for i := range g {
g[i] = make([]int, n)
dist[i] = 1 << 30
}
for i := range g {
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
t := abs(x1-x2) + abs(y1-y2)
g[i][j] = t
g[j][i] = t
}
}
dist[0] = 0
for i := 0; i < n; i++ {
j := -1
for k := 0; k < n; k++ {
if !vis[k] && (j == -1 || dist[k] < dist[j]) {
j = k
}
}
vis[j] = true
ans += dist[j]
for k := 0; k < n; k++ {
if !vis[k] {
dist[k] = min(dist[k], g[j][k])
}
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
# Accepted solution for LeetCode #1584: Min Cost to Connect All Points
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
g = [[0] * n for _ in range(n)]
dist = [inf] * n
vis = [False] * n
for i, (x1, y1) in enumerate(points):
for j in range(i + 1, n):
x2, y2 = points[j]
t = abs(x1 - x2) + abs(y1 - y2)
g[i][j] = g[j][i] = t
dist[0] = 0
ans = 0
for _ in range(n):
i = -1
for j in range(n):
if not vis[j] and (i == -1 or dist[j] < dist[i]):
i = j
vis[i] = True
ans += dist[i]
for j in range(n):
if not vis[j]:
dist[j] = min(dist[j], g[i][j])
return ans
// Accepted solution for LeetCode #1584: Min Cost to Connect All Points
struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
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, mut i: usize, mut j: usize) -> bool {
i = self.find(i);
j = self.find(j);
if i != j {
self.parent[i] = j;
self.n -= 1;
true
} else {
false
}
}
}
impl Solution {
fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut queue: BinaryHeap<(Reverse<i32>, usize, usize)> = BinaryHeap::new();
for i in 0..n {
for j in i + 1..n {
queue.push((Reverse(Self::dist(&points[i], &points[j])), i, j));
}
}
let mut uf = UnionFind::new(n);
let mut res = 0;
while let Some((Reverse(d), i, j)) = queue.pop() {
if uf.union(i, j) {
res += d;
}
if uf.n == 1 {
break;
}
}
res
}
fn dist(a: &[i32], b: &[i32]) -> i32 {
(a[0] - b[0]).abs() + (a[1] - b[1]).abs()
}
}
#[test]
fn test() {
let points = vec_vec_i32![[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]];
let res = 20;
assert_eq!(Solution::min_cost_connect_points(points), res);
let points = vec_vec_i32![[3, 12], [-2, 5], [-4, 1]];
let res = 18;
assert_eq!(Solution::min_cost_connect_points(points), res);
let points = vec_vec_i32![[0, 0], [1, 1], [1, 0], [-1, 1]];
let res = 4;
assert_eq!(Solution::min_cost_connect_points(points), res);
let points = vec_vec_i32![[-1000000, -1000000], [1000000, 1000000]];
let res = 4000000;
assert_eq!(Solution::min_cost_connect_points(points), res);
let points = vec_vec_i32![[0, 0]];
let res = 0;
assert_eq!(Solution::min_cost_connect_points(points), res);
}
// Accepted solution for LeetCode #1584: Min Cost to Connect All Points
function minCostConnectPoints(points: number[][]): number {
const n = points.length;
const g: number[][] = Array(n)
.fill(0)
.map(() => Array(n).fill(0));
const dist: number[] = Array(n).fill(1 << 30);
const vis: boolean[] = Array(n).fill(false);
for (let i = 0; i < n; ++i) {
const [x1, y1] = points[i];
for (let j = i + 1; j < n; ++j) {
const [x2, y2] = points[j];
const t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
g[i][j] = t;
g[j][i] = t;
}
}
let ans = 0;
dist[0] = 0;
for (let i = 0; i < n; ++i) {
let j = -1;
for (let k = 0; k < n; ++k) {
if (!vis[k] && (j === -1 || dist[k] < dist[j])) {
j = k;
}
}
vis[j] = true;
ans += dist[j];
for (let k = 0; k < n; ++k) {
if (!vis[k]) {
dist[k] = Math.min(dist[k], g[j][k]);
}
}
}
return ans;
}
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.