Min Cost to Connect Points

shriyanshi24jindal

Mar 30th, 2026

124

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.68 KB | None | 0 0

copy raw download clone embed print report

class Pair
{
int vertex;
int weight;
Pair(int weight, int vertex)
{
this.weight = weight;
this.vertex = vertex;
}
}
class Solution {
public int minCostConnectPoints(int[][] points) {
int V = points.length;
// Step-1 Create an adjacency list: each node has (weight, neighbor)
List<List<int[]>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<>());
}
// Step-2 build edges
for(int i=0; i<V; i++)
{
for(int j=i+1; j<V; j++)
{
int weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
adj.get(i).add(new int[]{weight, j});
adj.get(j).add(new int[]{weight, i}); // undirected
}
}
// Step-3 Create a visited array
boolean[] visited = new boolean[V];
// Step-4 Define a min-heap <weight, node>
PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.weight, y.weight));
pq.offer(new Pair(0, 0));
int sum = 0;
while(!pq.isEmpty())
{
Pair pair = pq.poll();
int currentNode = pair.vertex;
int currentWeight = pair.weight;
if(visited[currentNode])
continue;
visited[currentNode] = true;
sum += currentWeight;
// traverse neighbour nodes
for(int[] neighbour : adj.get(currentNode))
{
int vertex = neighbour[1];
int weight = neighbour[0];
if(visited[vertex] == false)
{
pq.add(new Pair(weight, vertex));
}
}
}
return sum;
}
}

RAW Paste Data Copied

class Pair
{
    int vertex;
    int weight;
    Pair(int weight, int vertex)
    {
        this.weight = weight;
        this.vertex = vertex;
    }
}

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int V = points.length;

// Step-1 Create an adjacency list: each node has (weight, neighbor)
        List<List<int[]>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<>());
        }
        
        // Step-2 build edges
        for(int i=0; i<V; i++) 
        {
            for(int j=i+1; j<V; j++) 
            {
                int weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);

adj.get(i).add(new int[]{weight, j});
                adj.get(j).add(new int[]{weight, i}); // undirected
            }
        }

// Step-3 Create a visited array
        boolean[] visited = new boolean[V];
    
        // Step-4 Define a min-heap <weight, node> 
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.weight, y.weight));
        pq.offer(new Pair(0, 0));
        int sum = 0;

while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.vertex;
            int currentWeight = pair.weight;

if(visited[currentNode])
                continue;
            
            visited[currentNode] = true;
            sum += currentWeight;

// traverse neighbour nodes
            for(int[] neighbour : adj.get(currentNode))
            {
                int vertex = neighbour[1];
                int weight = neighbour[0];
                if(visited[vertex] == false)
                {
                    pq.add(new Pair(weight, vertex));
                }
            }
        }
        return sum;
    }
}