DSA Tracker

Problem

Pattern this teaches:Minimum Spanning Tree and Graph Greedy

Medium

Min Cost to Connect All Points

A medium Graph interview guide. Task statement, worked examples, intuition, and step-by-step solutions.

Topic
Graph
Sheets
1
Core for
12 roles
PracticeWatch it step by step

The problem

Given a weighted undirected graph with n nodes and a list of edges [u, v, weight], find the minimum spanning tree using Prim's algorithm and return the total weight.

Example 1

Input
n = 5, edges = [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]
Output
16
Why
MST uses edges (0,1)=2, (1,2)=3, (1,4)=5, (0,3)=6. Total = 16.

Example 2

Input
n = 4, edges = [[0,1,1],[0,2,4],[1,2,2],[1,3,6],[2,3,3]]
Output
6
Why
MST uses edges (0,1)=1, (1,2)=2, (2,3)=3. Total = 6.

Constraints

  • 1 <= n <= 100
  • 0 <= edges.length <= n * (n - 1) / 2
  • 1 <= edge weight <= 1000

How to think about it

Updated 2026-09-29

Maintain a visited cut boundary that expands one node at a time. The cut property ensures that greedily taking the minimum-weight edge crossing the boundary into an unvisited vertex never makes a suboptimal choice. A min-heap ensures the cheapest crossing edge is extracted in logarithmic time.

Approaches, worst first

  1. Linear scan candidate key selection

    time O(V^2) · space O(V)

    Track the minimum connecting edge weight to each unvisited vertex in a linear distance array. In each of the n iterations, scan all unvisited vertices to extract the minimum edge, mark it visited, and update adjacent boundary weights. Linear scanning incurs quadratic time on sparse topologies.

  2. Priority queue with visited setWrite this one

    time O(E log V) · space O(V + E)

    Build an undirected adjacency list with edge weights. Push `(0, 0)` into a min-heap. Pop the cheapest edge `(w, u)`. If u is visited, skip it; otherwise mark u visited, add w to total MST weight, and push each neighbor `(edgeWeight, v)` for all unvisited v.

Where people lose marks · 3
  • Neglecting to skip already visited vertices when popping from the priority queue leads to redundant edge additions and duplicate weight accumulation.
  • Undirected edges must be recorded in both directions `(u -> v)` and `(v -> u)` in adjacency lists.
  • When the graph has disconnected components and cannot span all n vertices, Prim cannot find a single spanning tree.

Full solution

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

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    if (n <= 1) return 0;
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    int total_cost = 0;
    int connected = 0;
    while (!pq.empty() && connected < n) {
        auto [cost, u] = pq.top();
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        total_cost += cost;
        connected++;
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                int dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                pq.push({dist, v});
            }
        }
    }
    return total_cost;
}
Java
import java.util.*;

public class Main {
    static int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n <= 1) return 0;
        boolean[] visited = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0});
        int totalCost = 0;
        int connected = 0;
        while (!pq.isEmpty() && connected < n) {
            int[] top = pq.poll();
            int cost = top[0], u = top[1];
            if (visited[u]) continue;
            visited[u] = true;
            totalCost += cost;
            connected++;
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    int dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                    pq.offer(new int[]{dist, v});
                }
            }
        }
        return totalCost;
    }
}
Python
import heapq

def min_cost_connect_points(points):
    n = len(points)
    if n <= 1:
        return 0
    visited = [False] * n
    pq = [(0, 0)]  # (cost, node)
    total_cost = 0
    connected = 0

    while pq and connected < n:
        cost, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total_cost += cost
        connected += 1
        x1, y1 = points[u]
        for v in range(n):
            if not visited[v]:
                x2, y2 = points[v]
                dist = abs(x1 - x2) + abs(y1 - y2)
                heapq.heappush(pq, (dist, v))

    return total_cost
JavaScript
function minCostConnectPoints(points) {
  const n = points.length;
  if (n <= 1) return 0;

  const edges = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
      edges.push([dist, i, j]);
    }
  }

  edges.sort((a, b) => a[0] - b[0]);

  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  let totalCost = 0;
  let edgesCount = 0;

  for (const [dist, u, v] of edges) {
    const rootU = find(u);
    const rootV = find(v);
    if (rootU !== rootV) {
      parent[rootU] = rootV;
      totalCost += dist;
      edgesCount++;
      if (edgesCount === n - 1) break;
    }
  }

  return totalCost;
}
Try it in the editor

The theory behind it

Graph — the ground this problem stands on. All Graph problems

What Graph is

A graph is a network of individual points, called vertices or nodes, connected by lines called edges. Think of a subway transit map, an electrical circuit, or a web of social friends. Unlike a tree, a graph has no designated top node and no parent-child hierarchy. Connections can run one-way or both ways, and paths can loop back on themselves to form closed cycles.

When to reach for it

Reach for graph algorithms when inputs describe relationships, networks, flights between cities, course prerequisites, or clone networks. Signals include finding the shortest route across unweighted connections, ordering tasks that depend on earlier tasks, counting isolated clusters, or checking whether a path contains an infinite loop. Whenever problems present pairs of related entities and ask for reachability, distances, or dependencies, graph representations apply.

How the pattern works

First convert edge lists into an adjacency list, mapping each node to an array of its neighbors. Choose your exploration strategy based on the goal: use a queue and breadth-first search to find the shortest path in unweighted networks, or use recursion and depth-first search to explore full paths and detect cycles. Because graphs can have loops, always track visited nodes in a set or boolean array. Add nodes to the visited set at the moment they enter the queue so they are never visited twice.

More Graph problems

Minimum Number of Days to Disconnect IslandHardShortest Path in Directed Acyclic GraphMediumWord Ladder IIHardRemove Stones to Minimize the TotalMediumNumber of Islands IIHardMost Stones Removed with Same Row or ColumnMediumCount Unreachable Pairs of Nodes in an Undirected GraphMediumMaximum Connected with One ChangeHard

Interactive Practice

PracticeWatch step-by-step visualizer

Target Roles

Core requirement for 12 roles:

SDE / Software EngineerBackend EngineerData EngineerGame DeveloperSecurity EngineerSite Reliability EngineerCloud EngineerComputer Vision EngineerRobotics EngineerCompiler / PL Engineer

Track in your role's order

Pick your target role and all 370 problems resequence to what that interview actually asks.

Start free

Problem set and role mapping as of .