#1584

Medium

LeetCode Problem Workspace

Min Cost to Connect All Points

Min Cost to Connect All Points asks for the minimum cost to connect all points on a 2D plane, using manhattan distances between points.

array union find graph minimum spanning tree

Problem Statement

You are given a set of points on a 2D-plane where each point is represented as [xi, yi]. The task is to find the minimum cost required to connect all these points such that there exists exactly one simple path between any two points.

The cost to connect two points [xi, yi] and [xj, yj] is defined as the Manhattan distance: |xi - xj| + |yi - yj|. Your goal is to determine the minimum total cost to connect all points using these distances.

Examples

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output: 20

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

Example details omitted.

Constraints

1 <= points.length <= 1000
-106 <= xi, yi <= 106
All pairs (xi, yi) are distinct.

Solution Approach

Graph Representation

We can treat the problem as a graph, where each point is a node and each pair of points has an edge weighted by their Manhattan distance. The objective is to find the minimum spanning tree (MST) of this graph, which will give the minimal cost to connect all points.

Union-Find Algorithm

To efficiently solve this, we use the union-find (also known as disjoint-set) data structure. This allows us to track which points are already connected, merging sets as we add edges and ensuring we don't form cycles in the MST.

Kruskal's Algorithm

We can apply Kruskal's algorithm to find the MST. This involves sorting all possible edges by their Manhattan distance and using union-find to add edges one by one, ensuring no cycles are formed and all points get connected.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the approach used to sort the edges and apply the union-find operations. Sorting the edges takes O(E log E), where E is the number of edges (in this case, O(n^2) for n points). The union-find operations are nearly constant time with path compression and union by rank, making the overall complexity approximately O(n^2 log n). Space complexity is O(n) for the union-find structure and storing the graph edges.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

What if the points are in 3D space? The approach can be extended, but the distance formula changes to account for the z-axis.
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.
What if the points are already pre-sorted? This might optimize the edge construction process but does not change the core algorithm.

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

Continue Practicing

#1632 rank transform of a matrix #1489 find critical and pseudo critical edges in minimum spanning tree #1697 checking existence of edge length limited paths