Min Cost To Connect All Points - Leetcode Solution

Problem Statement:

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:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as follows:

• [0,0] connects [2,2] which connects [5,2] and [7,0]
• [3,10] connects [5,2] The resulting cost is 2 + 8 + 10 = 20.

Solution:

The problem requires us to find the minimum cost to connect all points on a 2D plane. 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.

We can solve the problem using Kruskal's Algorithm in the following way:

• Create an empty list of edges.
• Create a list of all pairs of points and calculate their distance. Add each pair with their respective distance to the list of edges.
• Sort the list of edges in ascending order.
• Create a list of disjoint sets for the points.
• Traverse through the edges in the sorted list and check if the two points of an edge belong to the same disjoint set. If not, union the sets and add the edge to the final minimum spanning tree.
• The total cost of the minimum spanning tree will be the minimum cost to connect all points.

The time complexity of the algorithm is O(N^2logN), where N is the number of points.

Implementation:

Here's the implementation of the above algorithm:

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def find(parent, i):
            if parent[i] == i:
                return i
            return find(parent, parent[i])

        def union(parent, rank, x, y):
            xroot = find(parent, x)
            yroot = find(parent, y)
            if rank[xroot] < rank[yroot]:
                parent[xroot] = yroot
            elif rank[xroot] > rank[yroot]:
                parent[yroot] = xroot
            else:
                parent[yroot] = xroot
                rank[xroot] += 1

        n = len(points)
        edges = []
        for i in range(n):
            for j in range(i+1, n):
                distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((distance, i, j))
        edges.sort()
        parent = [i for i in range(n)]
        rank = [0] * n
        mst = []
        cost = 0
        for edge in edges:
            if len(mst) == n-1:
                break
            distance, u, v = edge
            if find(parent, u) != find(parent, v):
                union(parent, rank, u, v)
                cost += distance
                mst.append(edge)

        return cost

We loop through all pairs of points and calculate the distance. We create an edge list with all distances and sort it in ascending order. We use union-find to determine if 2 vertices are in the same family. If they are not, we calculate the cost of including the edge in the MST and add it to a total cost variable.

1