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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Min Cost to Connect All Points

Number: 1706

Difficulty: Medium

Paid? No

Companies: TikTok, Uber, Nutanax, Amazon, Microsoft, Adobe, Directi

Problem Description

Given an array of points representing coordinates on a 2D-plane, our goal is to connect all the points such that the cost of connecting any two points is defined by their Manhattan distance. We want to create a configuration (a tree) where there is exactly one simple path between any two points, and the total cost is minimized. This is essentially a Minimum Spanning Tree (MST) problem on a complete graph where the vertices are the points and the edge costs are the Manhattan distances between points.

Key Insights

  • The problem can be reinterpreted as finding a Minimum Spanning Tree (MST) on a complete graph.
  • Manhattan distance is used to calculate the weight/cost between every pair of vertices.
  • Prim’s or Kruskal’s algorithm can be applied to solve the MST problem.
  • A direct construction of the complete graph is unnecessary; distances can be computed on the fly, which is efficient given the problem constraints.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

We can solve the problem using Prim’s algorithm. We start from an arbitrary point (for example, the first point) and iteratively add the point that has the smallest distance to the growing MST. Instead of explicitly constructing all the edges, we compute the Manhattan distance on the fly between the current MST and the remaining points. An array is used to track the minimum connection cost for each point that is not yet included in the tree. At each iteration, we select the point with the smallest cost to add into the MST and update the costs for the remaining points. This approach guarantees that we connect all points with the minimum total cost.

Code Solutions

# Python solution using Prim's algorithm

class Solution:
    def minCostConnectPoints(self, points):
        # number of points
        n = len(points)
        # initialize cost for each point as infinity, except the first point
        minCost = [float('inf')] * n
        minCost[0] = 0  # start from the first point
        
        # keep track of which points are included in the MST
        inMST = [False] * n
        
        # total cost of connecting all points
        total_cost = 0
        
        for _ in range(n):
            # select the next point with the smallest connection cost
            curr = -1
            curr_cost = float('inf')
            for i in range(n):
                if not inMST[i] and minCost[i] < curr_cost:
                    curr = i
                    curr_cost = minCost[i]
            
            # add the cost of the chosen point
            total_cost += curr_cost
            inMST[curr] = True
            
            # update the connection costs for the remaining points
            for next_point in range(n):
                if not inMST[next_point]:
                    # compute the Manhattan distance between the current and next point
                    (x1, y1), (x2, y2) = points[curr], points[next_point]
                    dist = abs(x1 - x2) + abs(y1 - y2)
                    if dist < minCost[next_point]:
                        minCost[next_point] = dist
        
        return total_cost

# Example usage:
# sol = Solution()
# print(sol.minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]]))
← Back to All Questions