- Traverse all edges once, add up the lengths of the edges and return the sum as the result.

- If you are familiar with the**Union-Find** algorithm, it is easy to solve the problem with_Kruskal's algorithm_. However, this problem does not directly give the`edges` information, and we need to calculate it through the vertex information, which is not difficult, but this causes the algorithm to run slower than_Prim's Algorithm_ because there are too many edges. The more edges, the slower_Kruskal's Algorithm_.

`E` is the`edges.length`.

For this problem,`points` are given, so using`Prim's Algorithm` would be faster and easier to understand.

Because if we use`Kruskal's Algorithm`, we have to convert`points` into`edges`, and we will get a fully dense graph.

`N` isthe`points.length`.

The more edges there are,theworse the performance of`Kruskal's Algorithm` will be.

* Time:`O(E * logE)`.

* Space:`O(N * N)`.

For sparse graphs,`Kruskal's Algorithm` is much more efficient than`Prim's Algorithm`.

For problems of`Minimum Spanning Tree` which`edges` are given, we can give priority to using_Kruskal's Algorithm_.

* Time:`O(E * log(E))`.

* Space:`O(V * V)`.

The following code can also be implemented by using`heap sort`, but it would be slower.

from collectionsimport deque

classSolution:

def__init__(self):

self.parents= []

defminCostConnectPoints(self,points: List[List[int]]) ->int:

self.parents=list(range(len(points)))

result=0

edged_points= []

edges= []

for i, pointinenumerate(points):

for jinrange(i+1,len(points)):

distance=abs(point[0]- points[j][0])+ \

abs(point[1]- points[j][1])

heapq.heappush(edged_points, (distance, i, j))

edges.append((distance, i, j))

edges.sort()

edges= deque(edges)

while edges:

distance, i, j= edges.popleft()

while edged_points:

distance, i, j= heapq.heappop(edged_points)

ifself.is_same_root(i, j):

self.unite(i, j)

result+= distance

return result

defunite(self,x,y):

root_x=self.find_root(x)

root_y=self.find_root(y)

if x== parent:

return x

root=self.find_root(parent)

self.parents[x]= root

*`visited` is also not needed, because each`heappop()` means that a point has been`visited`.

`n` is the`points.length`.

* Time:`O(n * n)`. All those solutions' time complexity are`O(n * n)`, because`heapq.heapify()` is`O(n)`.

* Space:`O(n)`.

`V` is the`points.length`.

* Time:`O(V * V)`. All those solutions' time complexity are`O(n * n)`, because`heapq.heapify()` is`O(n)`.

* Space:`O(V)`.

- Traverse all edges once, add up the lengths of the edges and return the sum as the result.

- If you are familiar with the**Union-Find** algorithm, it is easy to solve the problem with_Kruskal's algorithm_. However, this problem does not directly give the`edges` information, and we need to calculate it through the vertex information, which is not difficult, but this causes the algorithm to run slower than_Prim's Algorithm_ because there are too many edges. The more edges, the slower_Kruskal's Algorithm_.

`E` is the`edges.length`.

For this problem,`points` are given, so using`Prim's Algorithm` would be faster and easier to understand.

Because if we use`Kruskal's Algorithm`, we have to convert`points` into`edges`, and we will get a fully dense graph.

For sparse graphs,`Kruskal's Algorithm` is more efficient than`Prim's Algorithm`.

`N` is the`points.length`.

-`V` is the`points.length`.

-`E` is the`edges.length`. In this problem, the`E` is`V * V`.

* Time:`O(E *logE)`.

* Space:`O(N *N)`.

* Time:`O(E *log(E))`.

* Space:`O(V *V)`.

The following code can also be implemented by using`heap sort`, but it would be slower.

from collectionsimport deque

classSolution:

def__init__(self):

self.parents= []

defminCostConnectPoints(self,points: List[List[int]]) ->int:

self.parents=list(range(len(points)))

result=0

edged_points= []

edges= []

for i, pointinenumerate(points):

for jinrange(i+1,len(points)):

distance=abs(point[0]- points[j][0])+ \

abs(point[1]- points[j][1])

heapq.heappush(edged_points, (distance, i, j))

edges.append((distance, i, j))

edges.sort()

edges= deque(edges)

while edges:

distance, i, j= edges.popleft()

while edged_points:

distance, i, j= heapq.heappop(edged_points)

ifself.is_same_root(i, j):

self.unite(i, j)

result+= distance

return result

defunite(self,x,y):

root_x=self.find_root(x)

root_y=self.find_root(y)

if x== parent:

return x

root=self.find_root(parent)

self.parents[x]= root

*`visited` is also not needed, because each`heappop()` means that a point has been`visited`.

`n` is the`points.length`.

* Time:`O(n * n)`. All those solutions' time complexity are`O(n * n)`, because`heapq.heapify()` is`O(n)`.

* Space:`O(n)`.

`V` is the`points.length`.

* Time:`O(V * V)`. All those solutions' time complexity are`O(n * n)`, because`heapq.heapify()` is`O(n)`.

* Space:`O(V)`.