# 1584. Min Cost to Connect All Points

#### Medium

***

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`.

Return *the minimum cost to make all points connected.* All points are connected if there is **exactly one** simple path between any two points.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/26/d.png)

```
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.
Notice that there is a unique path between every pair of points.
```

**Example 2:**

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

 

**Constraints:**

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

#### Time Complexity : O(N^2)

```python
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        # Minimum Spanning Tree Prims Algo
        n = len(points)
        total_cost = 0
        edges_count = 0
        
        visited = [False]*n
        min_dist = [math.inf]*n
        min_dist[0] = 0 # Start Point
        
        while edges_count < n:
            current_min_edge = math.inf
            current_node = -1
            # Find node with minimum distance
            for node in range(n):
                if not visited[node] and min_dist[node] < current_min_edge:
                    current_node = node
                    current_min_edge = min_dist[node]
                
            total_cost += current_min_edge
            edges_count += 1
            visited[current_node] = True
            
            for next_node in range(n):
                weight = abs(points[current_node][0] - points[next_node][0]) + abs(points[current_node][1] - points[next_node][1])
                if not visited[next_node] and min_dist[next_node] > weight:
                    min_dist[next_node] = weight
        return total_cost
```