We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Min Cost to Connect All Points

Difficulty: Medium

Problem Description

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|. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Key Insights

  • The problem can be modeled as a Minimum Spanning Tree (MST) problem.
  • The Manhattan distance is used to calculate the cost between points.
  • Kruskal’s or Prim’s algorithm can be employed to find the MST efficiently.
  • Using a Union-Find data structure helps manage connected components.

Space and Time Complexity

Time Complexity: O(E log E) where E is the number of edges, which is O(n^2) in the worst case. Space Complexity: O(n) for storing the Union-Find structure.

Solution

The solution involves creating a graph where each point is a node and the edges are the Manhattan distances between every pair of points. We can use Kruskal’s algorithm to build the Minimum Spanning Tree. This involves sorting all edges based on their weights (distances) and using a Union-Find data structure to avoid cycles while connecting the points. The total cost will be the sum of the weights of the edges included in the MST.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1

def minCostConnectPoints(points):
    n = len(points)
    edges = []
    
    # Create all edges based on Manhattan distance
    for i in range(n):
        for j in range(i + 1, n):
            cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((cost, i, j))
    
    # Sort edges based on cost
    edges.sort()
    
    uf = UnionFind(n)
    total_cost = 0
    for cost, i, j in edges:
        if uf.find(i) != uf.find(j):  # If they are not connected
            uf.union(i, j)
            total_cost += cost
    
    return total_cost
← Back to All Questions