MediumNo. 1584
Min Cost to Connect All Points — LeetCode 1584 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Graph, Array, Minimum Spanning Tree
- On a study list
- NeetCode 150
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1584. Min Cost to Connect All Points is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0990 | Satisfiability of Equality Equations | Medium |
| 1489 | Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree | Hard |
| 1632 | Rank Transform of a Matrix | Hard |
| 1579 | Remove Max Number of Edges to Keep Graph Fully Traversable | Hard |
| 0547 | Number of Provinces | Medium |
Frequently asked questions
- How hard is LeetCode 1584. Min Cost to Connect All Points?
LeetCode 1584. Min Cost to Connect All Points is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1584. Min Cost to Connect All Points?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1584. Min Cost to Connect All Points?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1584. Min Cost to Connect All Points cover?
LeetCode 1584. Min Cost to Connect All Points is tagged Union Find, Graph, Array and Minimum Spanning Tree on LeetCode.