Intuition

This is a minimum spanning tree on a complete graph where edge weights are Manhattan distances. Prim’s algorithm grows the tree by repeatedly adding the cheapest edge to a new point.

Approach

Start from any point; track the min distance from the growing tree to each outside point.
Repeatedly pick the closest outside point, add its distance to the total, and mark it in the tree.
Update the distances of remaining points against the newly added one.

Complexity

Time — O(n^2): dense Prim’s over all point pairs.
Space — O(n): the distance and in-tree arrays.

Full Solution — all languages

class Solution:
    def minCostConnectPoints(self, grid):
        pts=grid; n=len(pts)
        if n<=1: return 0
        in_mst=[False]*n; dist=[float('inf')]*n; dist[0]=0; total=0
        for _ in range(n):
            u=-1
            for i in range(n):
                if not in_mst[i] and (u==-1 or dist[i]<dist[u]): u=i
            in_mst[u]=True; total+=dist[u]
            for v in range(n):
                if not in_mst[v]:
                    d=abs(pts[u][0]-pts[v][0])+abs(pts[u][1]-pts[v][1])
                    if d<dist[v]: dist[v]=d
        return total

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] grid) {
        int[][] pts=grid; int n=pts.length; if(n<=1)return 0; boolean[] inMst=new boolean[n]; long[] dist=new long[n]; Arrays.fill(dist,Long.MAX_VALUE); dist[0]=0; long total=0; for(int it=0;it<n;it++){int u=-1; for(int i=0;i<n;i++)if(!inMst[i]&&(u==-1||dist[i]<dist[u]))u=i; inMst[u]=true; total+=dist[u]; for(int v=0;v<n;v++)if(!inMst[v]){long d=Math.abs(pts[u][0]-pts[v][0])+Math.abs(pts[u][1]-pts[v][1]); if(d<dist[v])dist[v]=d;}} return (int)total;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& grid) {
        auto& pts=grid; int n=pts.size(); if(n<=1)return 0; vector<char> inMst(n,0); vector<long long> dist(n,LLONG_MAX); dist[0]=0; long long total=0; for(int it=0;it<n;it++){int u=-1; for(int i=0;i<n;i++)if(!inMst[i]&&(u==-1||dist[i]<dist[u]))u=i; inMst[u]=1; total+=dist[u]; for(int v=0;v<n;v++)if(!inMst[v]){long long d=abs(pts[u][0]-pts[v][0])+abs(pts[u][1]-pts[v][1]); if(d<dist[v])dist[v]=d;}} return (int)total;
    }
};

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minCostConnectPoints = function(grid) {
    const pts=grid,n=pts.length; if(n<=1)return 0; const inMst=new Array(n).fill(false),dist=new Array(n).fill(Infinity); dist[0]=0; let total=0; for(let it=0;it<n;it++){let u=-1; for(let i=0;i<n;i++)if(!inMst[i]&&(u===-1||dist[i]<dist[u]))u=i; inMst[u]=true; total+=dist[u]; for(let v=0;v<n;v++)if(!inMst[v]){const d=Math.abs(pts[u][0]-pts[v][0])+Math.abs(pts[u][1]-pts[v][1]); if(d<dist[v])dist[v]=d;}} return total;
};

Min Cost to Connect All Points

Example 1

Example 2

Constraints