#1584

Min Cost to Connect All Points

pupil · 550 · lc medium +28 · verified · 70.4% accepted · 5,592 likes · top 79%

⚑ Minimum Spanning Tree (Kruskal's / Prim's)

Description

You are given an array points representing 2D coordinates. The cost to connect two points is the Manhattan distance |xi - xj| + |yi - yj|. Return the minimum total cost to connect all points such that every point is reachable from every other point.

Example 1:

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

Output: 20

Explanation:

Example 2:

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 3:

Input: points = [[3,12],[-2,5],[-4,1]]

Output: 18

Code

1

2

3

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int: