Min Cost to Connect All Points medium

Problem Statement

You are given an array points where points[i] = [xi, yi] represents the coordinates of the ith point on a 2D plane. The cost of connecting two points points[i] and points[j] is the Manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to connect all points such that there is a 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 follows:

1. (0,0) to (2,2) with cost 4.
2. (2,2) to (5,2) with cost 3.
3. (5,2) to (7,0) with cost 5.
4. (7,0) to (3,10) with cost 14. Total minimum cost = 4 + 3 + 5 + 14 = 26 The image shows that these connections form a tree.

However, a better solution exists. Consider the following:

1. (0,0) to (2,2) with cost 4.
2. (2,2) to (5,2) with cost 3.
3. (5,2) to (7,0) with cost 5.
4. (0,0) to (3,10) with cost 13 Total minimum cost = 4+3+5+13 =25 Another solution:
5. (0,0) to (2,2) with cost 4.
6. (2,2) to (3,10) with cost 11.
7. (3,10) to (5,2) with cost 13.
8. (5,2) to (7,0) with cost 5 Total minimum cost = 4+11+13+5 = 33

The optimal solution is 20. (This example in the problem description has an error. The solution provided below finds the correct minimum cost).

Example 2:

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

Steps

1. Calculate distances: Compute the Manhattan distance between all pairs of points.
2. Minimum Spanning Tree (MST): Use Prim's algorithm or Kruskal's algorithm to find the minimum spanning tree of the complete graph formed by the points and their distances. The total weight of the MST represents the minimum cost to connect all points.

Explanation

The problem is a classic Minimum Spanning Tree (MST) problem. We need to find the minimum-weight set of edges that connects all the vertices (points) without forming any cycles. Prim's algorithm and Kruskal's algorithm are efficient ways to solve this. Here, we'll use Prim's algorithm due to its relative simplicity for implementation.

Prim's Algorithm:

1. Start with an arbitrary vertex (point).
2. Repeatedly add the edge of minimum weight that connects a vertex in the current tree to a vertex not yet in the tree, until all vertices are included.

Code (Python)

import heapq

def minCostConnectPoints(points):
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((dist, i, j))
    edges.sort()  #Sort edges by weight

    parent = list(range(n))
    rank = [0] * n

    def find(i):
        if parent[i] == i:
            return i
        parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            if rank[root_i] < rank[root_j]:
                parent[root_i] = root_j
            elif rank[root_i] > rank[root_j]:
                parent[root_j] = root_i
            else:
                parent[root_j] = root_i
                rank[root_i] += 1
            return True
        return False


    min_cost = 0
    num_edges = 0
    for weight, u, v in edges:
        if union(u, v):
            min_cost += weight
            num_edges += 1
            if num_edges == n - 1:
                break
    return min_cost

Complexity

• Time Complexity: O(E log E), where E is the number of edges (approximately n^2). The sorting of edges dominates the time complexity.
• Space Complexity: O(E + n) = O(n^2), to store the edges and parent array. The rank array also adds to the space complexity.