Problem Description

The problem is to find the minimum cost to connect all points in a 2D plane such that there is exactly one simple path between any two points. The cost of connecting two points is the Manhattan distance between them (|xi - xj| + |yi - yj|). This is essentially finding the Minimum Spanning Tree (MST) of a complete graph where the vertices are the points and the edge weights are the Manhattan distances.

Solutions

Two main approaches are presented to solve this problem: Prim's Algorithm and Kruskal's Algorithm. Both are used to find the Minimum Spanning Tree.

Solution 1: Prim's Algorithm

This solution uses Prim's algorithm to find the MST.

Approach:

1. Construct Adjacency Matrix: Create an adjacency matrix g representing the graph where g[i][j] stores the Manhattan distance between point i and point j. The distance is calculated using abs(x1 - x2) + abs(y1 - y2).

2. Prim's Algorithm: Implement Prim's algorithm using a dist array to keep track of the minimum distance from the MST to each vertex and a vis array to mark visited vertices.

   • Initialize dist[0] to 0 and all other distances to infinity.
   • Iteratively select the unvisited vertex i with the minimum distance.
   • Add i to the MST, updating ans (the total cost).
   • Update the distances of its unvisited neighbors.

Time Complexity: O(N^2), where N is the number of points. Prim's algorithm with a min-heap would improve this to O(E log V), but since it's a complete graph E = V^2, it would still be O(N^2 log N). This implementation uses a simpler approach without a heap for better clarity.

Space Complexity: O(N^2) for the adjacency matrix.

Solution 2: Kruskal's Algorithm

This solution uses Kruskal's algorithm, a disjoint-set based approach, to find the MST.

Approach:

1. Create Edges: Generate all edges between pairs of points and store them in a list g. Each edge is represented as a tuple (cost, i, j) where cost is the Manhattan distance between points i and j.

2. Sort Edges: Sort the edges in ascending order of cost.

3. Kruskal's Algorithm: Implement Kruskal's algorithm using a disjoint-set data structure (find and union functions). Iterate through the sorted edges. If the two vertices of an edge belong to different sets (not connected), add the edge to the MST, union the sets, and update ans.

Time Complexity: O(E log E + Eα(E)) where E is the number of edges and α is the inverse Ackermann function. Since E = N^2, the complexity becomes O(N^2 log N). The sort function dominates.

Space Complexity: O(E) for the edge list and O(N) for the disjoint-set data structure.

Code Examples (Python)

Solution 1 (Prim's Algorithm):

import math
 
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        g = [[0] * n for _ in range(n)]
        dist = [math.inf] * n
        vis = [False] * n
        for i, (x1, y1) in enumerate(points):
            for j in range(i + 1, n):
                x2, y2 = points[j]
                g[i][j] = g[j][i] = abs(x1 - x2) + abs(y1 - y2)
        dist[0] = 0
        ans = 0
        for _ in range(n):
            mn = math.inf
            cur = -1
            for i in range(n):
                if not vis[i] and dist[i] < mn:
                    mn = dist[i]
                    cur = i
            vis[cur] = True
            ans += mn
            for i in range(n):
                if not vis[i]:
                    dist[i] = min(dist[i], g[cur][i])
        return ans

Solution 2 (Kruskal's Algorithm):

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
 
        n = len(points)
        g = []
        for i, (x1, y1) in enumerate(points):
            for j in range(i + 1, n):
                x2, y2 = points[j]
                g.append((abs(x1 - x2) + abs(y1 - y2), i, j))
        g.sort()
        p = list(range(n))
        ans = 0
        for cost, i, j in g:
            pa, pb = find(i), find(j)
            if pa != pb:
                p[pa] = pb
                ans += cost
        return ans
 

The code examples in other languages (Java, C++, Go, TypeScript) follow similar structures, implementing either Prim's or Kruskal's algorithm appropriately. The key differences lie in the syntax and standard library functions used for things like sorting, adjacency matrix representation, and disjoint-set implementations.