Minimum Cost to Connect All Points — Prim's on Complete Graph

Problem (LeetCode 1584)

Given points[i] = [xi, yi], connect all points with minimum total Manhattan distance cost (each connection costs |xi-xj| + |yi-yj|).

Solution

Python — Prim's O(n²)

import heapq

def minCostConnectPoints(points):
    n = len(points)
    visited = [False]*n
    heap = [(0, 0)]
    total = 0
    count = 0
    while count < n:
        cost, u = heapq.heappop(heap)
        if visited[u]: continue
        visited[u] = True
        total += cost
        count += 1
        for v in range(n):
            if not visited[v]:
                d = abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
                heapq.heappush(heap, (d, v))
    return total

JavaScript

function minCostConnectPoints(points) {
    const n=points.length, vis=new Array(n).fill(false);
    const heap=[[0,0]]; let total=0,cnt=0;
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;return heap.splice(mi,1)[0];};
    while(cnt<n){
        const[cost,u]=pop(); if(vis[u])continue; vis[u]=true; total+=cost; cnt++;
        for(let v=0;v<n;v++)if(!vis[v]){const d=Math.abs(points[u][0]-points[v][0])+Math.abs(points[u][1]-points[v][1]);heap.push([d,v]);}
    }
    return total;
}

Java

import java.util.*;
public int minCostConnectPoints(int[][] pts) {
    int n=pts.length; boolean[] vis=new boolean[n];
    PriorityQueue<int[]>pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{0,0}); int total=0,cnt=0;
    while(cnt<n){int[]top=pq.poll();int cost=top[0],u=top[1];if(vis[u])continue;vis[u]=true;total+=cost;cnt++;
        for(int v=0;v<n;v++)if(!vis[v])pq.offer(new int[]{Math.abs(pts[u][0]-pts[v][0])+Math.abs(pts[u][1]-pts[v][1]),v});}
    return total;
}

C++

#include <vector>
#include <queue>
using namespace std;
int minCostConnectPoints(vector<vector<int>>&pts){
    int n=pts.size(); vector<bool>vis(n,false);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>pq;
    pq.push({0,0}); int total=0,cnt=0;
    while(cnt<n){auto[cost,u]=pq.top();pq.pop();if(vis[u])continue;vis[u]=true;total+=cost;cnt++;
        for(int v=0;v<n;v++)if(!vis[v])pq.push({abs(pts[u][0]-pts[v][0])+abs(pts[u][1]-pts[v][1]),v});}
    return total;
}

C

/* C: array-based key[] Prim — O(n²) with no heap */