Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Min Cost to Connect All Points

Min Cost to Connect All Points explained: a minimum spanning tree over Manhattan distances with Prim's algorithm. Tested Python code and a live MST visual.

Also searched as: minimum spanning tree with Prim's algorithm · Kruskal vs Prim on points with Manhattan distance

🌲

Try it live Free

Minimum Spanning Tree: Kruskal vs Prim

In the MST lab, step through Prim growing one tree by always taking the cheapest edge out, and compare it with Kruskal skipping edges that would close a cycle.

Also useful: Union-Find (DSU), Binary Heap & Priority Queue

Open the playground →

The problem

Given points on a 2D plane, connecting two points costs their Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all points so that every point can reach every other.

Inputpoints = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output20

The key insight

The cheapest way to connect everything, with no wasted links, is a minimum spanning tree. Every pair of points is a possible edge, so the graph is dense. Prim's algorithm grows one tree from a start point, always adding the cheapest edge leaving the tree; with an O(n²) array version you never even build the edge list.

Brute force first: Trying every subset of n - 1 edges and checking it connects everything is exponential.

Step-by-step approach

  1. Keep dist[i] = cheapest known cost to attach point i to the tree; start with point 0 at 0, all others at infinity.
  2. Repeat n times: pick the unvisited point with the smallest dist.
  3. Mark it in the tree and add its dist to the total.
  4. Update every unvisited point's dist with its Manhattan distance to the newly added point, if smaller.
  5. Return the total.

Python solution

PYTHON 3tested
def min_cost_connect_points(points):
    n = len(points)
    in_tree = [False] * n
    dist = [float("inf")] * n          # cheapest edge from tree to each point
    dist[0] = 0
    total = 0
    for _ in range(n):
        u = min((i for i in range(n) if not in_tree[i]), key=dist.__getitem__)
        in_tree[u] = True
        total += dist[u]
        ux, uy = points[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(ux - points[v][0]) + abs(uy - points[v][1])
                if d < dist[v]:
                    dist[v] = d
    return total

Complexity

TimeO(n²)
SpaceO(n)

Each of the n rounds scans all points once to pick the minimum and once to update distances. That beats Kruskal's O(n² log n) on this complete graph, and needs only O(n) extra arrays.

Common mistakes

Frequently asked questions

What is the time and space complexity of Min Cost to Connect All Points?

Prim's array version runs in O(n²) time and O(n) space. Kruskal on all n² edges is O(n² log n) time and O(n²) space, so Prim is the better fit for this dense graph.

Kruskal or Prim: which should I use?

Kruskal sorts edges and suits sparse graphs given as an edge list. Prim grows from a node and suits dense graphs, like all pairs of points here.

How is a minimum spanning tree different from shortest paths?

An MST minimises the total weight of edges needed to connect all nodes. Shortest paths minimise the distance from one source to each node; the two trees are usually different.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.