What is the main technique for solving Min Cost to Connect All Points?

The main technique involves treating the problem as a minimum spanning tree (MST) problem and using the union-find data structure to efficiently track and merge connected points.

How do you compute the cost to connect two points in this problem?

The cost is calculated using the Manhattan distance formula: |xi - xj| + |yi - yj|, where (xi, yi) and (xj, yj) are the coordinates of the two points.

Can you use other algorithms besides Kruskal’s for this problem?

Yes, you could apply Prim’s algorithm as an alternative, but Kruskal’s is typically more intuitive for problems involving sorting edges and union-find operations.

What is the time complexity of solving Min Cost to Connect All Points?

The time complexity is approximately O(n^2 log n) due to the sorting of edges and the union-find operations, where n is the number of points.

Is the union-find data structure critical for solving this problem?

Yes, union-find is essential for efficiently merging connected components and ensuring that no cycles are formed while minimizing the connection cost.

#1584

Medium

auto_awesome并查集

LeetCode 题解工作台

连接所有点的最小费用

给你一个 points 数组，表示 2D 平面上的一些点，其中 points[i] = [x i , y i ] 。连接点 [x i , y i ] 和点 [x j , y j ] 的费用为它们之间的曼哈顿距离： |x i - x j | + |y i - y j | ，其中 |val| 表示…

数组并查集图最小生成树

题目描述

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [x_i, y_i] 。

连接点 [x_i, y_i] 和点 [x_j, y_j] 的费用为它们之间的 曼哈顿距离 ：|x_i - x_j| + |y_i - y_j| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：

输入：points = [[3,12],[-2,5],[-4,1]]
输出：18

示例 3：

输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4

示例 4：

输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000

示例 5：

输入：points = [[0,0]]
输出：0

提示：

1 <= points.length <= 1000
-10⁶ <= x_i, y_i <= 10⁶
所有点 (x_i, y_i) 两两不同。

lightbulb

解题思路

方法一：朴素 Prim 算法

我们定义一个数组 $dist$ ，其中 $dist[i]$ 表示点 $i$ 到当前生成树的距离，初始时 $dist[0] = 0$ ，其余均为 $+\infty$ ，定义一个数组 $vis$ ，其中 $vis[i]$ 表示点 $i$ 是否在生成树中，初始时所有点均不在生成树中，定义一个二维数组 $g$ ，其中 $g[i][j]$ 表示点 $i$ 到点 $j$ 的距离，那么我们的目标是将所有点都加入到生成树中，且总费用最小。

我们每次从不在生成树中的点中选取一个距离最小的点 $i$ ，将点 $i$ 加入到生成树中，并将 $i$ 到其它点的距离更新到 $dist$ 数组中，直到所有点都在生成树中为止。

该算法适用于稠密图，时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should be familiar with the union-find data structure and its use in solving MST problems.
question_mark
Look for an understanding of Kruskal's algorithm and how it connects to the minimum spanning tree problem.
question_mark
The candidate should understand the time complexity of sorting edges and performing union-find operations, especially in terms of scalability.

warning

常见陷阱

外企场景

error
Forgetting to check for cycles when adding edges, which can lead to invalid solutions.
error
Inefficient implementation of union-find, leading to performance issues in larger datasets.
error
Not recognizing that the problem is a classical MST problem, which could lead to unnecessary complexity in the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the points are in 3D space? The approach can be extended, but the distance formula changes to account for the z-axis.
arrow_right_alt
What if the problem asks to return the number of distinct connected components rather than minimizing the cost? The union-find method would still be useful for counting components.
arrow_right_alt
What if the points are already pre-sorted? This might optimize the edge construction process but does not change the core algorithm.

help

常见问题

外企场景

继续练习

#1632 矩阵转换后的排名 #1489 找到最小生成树里的关键边和伪关键边 #1697 检查边长度限制的路径是否存在