How do you solve Min Cost to Connect All Points?

Build an adjacency list representing the complete graph with Manhattan distances. Use a min-heap initialized with the starting point (cost 0). Repeatedly pop the smallest edge from the heap, skip if the point is visited, otherwise add its cost to the result and push all edges from this point to unvisited neighbors into the heap. Continue until all points are visited. This yields the MST cost efficiently.

What pattern does Min Cost to Connect All Points use?

The Pattern: Heap / Priority Queue (Prim's Algorithm for MST) The Heuristic: Use a min-heap to greedily select the next minimum cost edge connecting the growing MST to unvisited nodes, dynamically generating edges to avoid storing the entire graph explicitly.

Min Cost to Connect All Points

Q: What is the time complexity of Min Cost to Connect All Points?

O(N^2 log N). Constructing the adjacency list requires O(N^2) to compute all pairwise Manhattan distances. The main loop runs until all N points are visited, and each edge insertion into the heap costs O(log N). Since each point can push up to O(N) edges, the total complexity is O(N^2 log N).

Problem

Given an array points where points[i] = [xi, yi] represents a point on the 2D plane, return the minimum cost to make all points connected such that there is exactly one simple path between any two points. The cost of connecting two points is the Manhattan distance between them.

1 ≤ points.length ≤ 1000
−10⁶ ≤ xi, yi ≤ 10⁶
All points are distinct

Example

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output: 20

The algorithm constructs a minimum spanning tree (MST) connecting all points with minimum total cost. It starts from point 0 with cost 0, adds edges to neighbors with their Manhattan distances, and uses a min-heap to greedily select the next edge with the smallest cost that connects a new point. The MST edges chosen are (0-1), (1-3), (3-4), and (1-2) with costs 4, 3, 5, and 8 respectively, summing to 20.

Approach

Straightforward Solution

A brute-force approach would consider all edges between points (O(N^2)) and run a standard MST algorithm like Kruskal's or Prim's. However, explicitly storing all edges is expensive and unnecessary.

Core Observation

The problem reduces to finding a minimum spanning tree (MST) over a complete graph where vertices are points and edge weights are Manhattan distances. The MST ensures all points are connected with minimum total edge cost.

Path to Optimal

Preview

Prim's algorithm can be adapted to this problem by dynamically computing edges from the current MST to unvisited points, using a min-heap to select the next minimal edge. This avoids storing all edges upfront and achieves O(N^2 log N) time by pushing edges lazily…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build an adjacency list representing the complete graph with Manhattan distances. Use a min-heap initialized with the starting point (cost 0)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N^2 log N)

Constructing the adjacency list requires O(N^2) to compute all pairwise Manhattan distances. The main loop runs until all N points are visited, and each edge insertion into the heap costs O(log N). Since each point can push up to O(N) edges, the total complexity is O(N^2 log N).

Space

O(N^2)

The adjacency list stores all edges between points, which is O(N^2). The min-heap can hold up to O(N^2) edges in the worst case. This space is necessary for this approach since the graph is complete.

Solution

Python

1import heapq
2
3class Solution:
  def minCostConnectPoints(self, points: list[list[int]]) -> int:
      N = len(points)
      adj = { i:[] for i in range(N) }
      for i in range(N):
          x1, y1 = points[i]
          for j in range(i + 1, N):
              x2, y2 = points[j]
              dist = abs(x1 - x2) + abs(y1 - y2)
              adj[i].append([dist, j])
              adj[j].append([dist, i])
14
      res = 0
      visit = set()
      min_heap = [[0, 0]] 
      while len(visit) < N:
          cost, i = heapq.heappop(min_heap)
          if i in visit:
              continue
          res += cost
          visit.add(i)
          for nei_cost, nei in adj[i]:
              if nei not in visit:
                  heapq.heappush(min_heap, [nei_cost, nei])
      return res

Step-by-Step Solution

1

Construct Complete Graph with Manhattan Distances

5N = len(points)
6adj = { i:[] for i in range(N) }
7for i in range(N):
8    x1, y1 = points[i]
9    for j in range(i + 1, N):
10        x2, y2 = points[j]
11        dist = abs(x1 - x2) + abs(y1 - y2)
12        adj[i].append([dist, j])
13        adj[j].append([dist, i])

Objective

To build an adjacency list representing all edges between points with their Manhattan distances as weights.

Key Insight

The problem models a complete graph where each point connects to every other with an edge weighted by Manhattan distance. Precomputing these distances and storing them in an adjacency list allows efficient access during MST construction. Although this requires O(N^2) time and space, it enables quick edge lookups during the main algorithm.

Interview Quick-Check

Core Logic

Compute Manhattan distance for every pair of points and store bidirectional edges in the adjacency list to represent the complete graph.

Complexity

This step takes O(N^2) time and space, which is acceptable given the problem constraints.

Common Pitfalls & Bugs

Forgetting to add edges in both directions (i to j and j to i) would break the undirected graph assumption.

2

Apply Prim's Algorithm Using a Min-Heap to Build MST

To iteratively select the minimum cost edge connecting the MST to an unvisited point, accumulating the total cost.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 17 Critical

min_heap = [[0, 0]]

Initialize min-heap with starting point 0 and cost 0.

Starting the MST from point 0 with zero cost seeds the algorithm and ensures the heap always has candidate edges.

Line 19 Critical

cost, i = heapq.heappop(min_heap)

Pop the smallest cost edge from the heap.

Selecting the minimal edge ensures the MST grows optimally by always adding the least costly connection.

Line 27 Critical

return res

Return the total cost of the MST after all points are connected.

The accumulated cost represents the minimum cost to connect all points with no cycles, fulfilling the problem requirement.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why does Prim's algorithm guarantee the minimum total cost to connect all points?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Min Cost to Connect All Points from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Min Cost to Connect All Points drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def minCostConnectPoints(self, points: list[list[int]]) -> int:`
5	`N = len(points)`
6	`adj = { i:[] for i in range(N) }`
7	`for i in range(N):`
8	`x1, y1 = points[i]`
9	`for j in range(i + 1, N):`
10	`x2, y2 = points[j]`
11	`dist = abs(x1 - x2) + abs(y1 - y2)`
12	`adj[i].append([dist, j])`
13	`adj[j].append([dist, i])`
14
15	`res = 0`
16	`visit = set()`
17	`min_heap = [[0, 0]]`
18	`while len(visit) < N:`
19	`cost, i = heapq.heappop(min_heap)`
20	`if i in visit:`
21	`continue`
22	`res += cost`
23	`visit.add(i)`
24	`for nei_cost, nei in adj[i]:`
25	`if nei not in visit:`
26	`heapq.heappush(min_heap, [nei_cost, nei])`
27	`return res`

5	`N = len(points)`
6	`adj = { i:[] for i in range(N) }`
7	`for i in range(N):`
8	`x1, y1 = points[i]`
9	`for j in range(i + 1, N):`
10	`x2, y2 = points[j]`
11	`dist = abs(x1 - x2) + abs(y1 - y2)`
12	`adj[i].append([dist, j])`
13	`adj[j].append([dist, i])`