Min Cost to Connect All Points

How it works

We want to connect all points so that the total cost is minimum, where the cost to connect two points is their Manhattan distance.
This is exactly a Minimum Spanning Tree (MST) problem:

• Think of each point as a node in a graph.
• Every pair of points has an edge with weight = Manhattan distance.
• We need the cheapest way to connect all nodes without forming unnecessary cycles → that’s an MST.

This solution uses Prim’s Algorithm (greedy MST building):

• Start from any node (here, node 0).
• Repeatedly add the closest unvisited node to the growing connected set.
• Keep track of the best (minimum) known distance from the current MST to every unvisited node.

Instead of building all edges (which would be too many), we compute distances on the fly and update the best known connection cost for each node.

---

Steps

1. Let n be the number of points.
2. Create:
   • visit[i] → whether point i is already included in the MST
   • dist[i] → the minimum cost to connect point i to the current MST (initialize all as infinity)
3. Start from node = 0 with total cost res = 0 and connected edges edges = 0.
4. While we have added fewer than n - 1 edges:
   1. Mark the current node as visited (added to MST).
   2. For every unvisited point i:
      • Compute cost to connect i from the current node
      • Update dist[i] = min(dist[i], cost)
   3. Choose nextNode as the unvisited point with the smallest dist[i].
   4. Add dist[nextNode] to res (we are connecting nextNode to the MST).
   5. Move node = nextNode and increment edges.
5. Return res as the total minimum cost.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n)

Things to watch for

Using Euclidean Distance Instead of Manhattan Distance

The problem specifies Manhattan distance |x1 - x2| + |y1 - y2|, not Euclidean distance. Using the wrong distance formula will produce incorrect edge weights and ultimately a wrong MST cost.

Forgetting to Handle Self-Loops in Edge Generation

When generating all edges between points, ensure you only create edges between distinct points (i.e., i != j). Including self-loops with zero cost can corrupt the Union-Find structure or cause infinite loops in some implementations.

Not Stopping After N-1 Edges in MST Construction

A spanning tree with n nodes has exactly n-1 edges. Continuing to add edges after the MST is complete wastes time and, in some implementations, can cause issues. Always track the number of edges added and stop once you reach n-1.

from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n, node = len(points), 0
        dist = [100000000] * n
        visit = [False] * n
        edges, res = 0, 0

        while edges < n - 1:
            visit[node] = True
            nextNode = -1
            for i in range(n):
                if visit[i]:
                    continue
                curDist = (abs(points[i][0] - points[node][0]) +
                           abs(points[i][1] - points[node][1]))
                dist[i] = min(dist[i], curDist)
                if nextNode == -1 or dist[i] < dist[nextNode]:
                    nextNode = i

            res += dist[nextNode]
            node = nextNode
            edges += 1

        return res

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), node = 0;
        vector<int> dist(n, 100000000);
        vector<bool> visit(n, false);
        int edges = 0, res = 0;

        while (edges < n - 1) {
            visit[node] = true;
            int nextNode = -1;
            for (int i = 0; i < n; i++) {
                if (visit[i]) continue;
                int curDist = abs(points[i][0] - points[node][0]) +
                               abs(points[i][1] - points[node][1]);
                dist[i] = min(dist[i], curDist);
                if (nextNode == -1 || dist[i] < dist[nextNode]) {
                    nextNode = i;
                }
            }
            res += dist[nextNode];
            node = nextNode;
            edges++;
        }
        return res;
    }
};