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:

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)

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