Introduction

Min Cost to Connect All Points is a classic Minimum Spanning Tree problem.

You are given:

  • Points on a 2D plane
  • Cost between two points = Manhattan Distance

Goal:

Connect all points with minimum total cost.

Example

Input

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

Output

20

Key Observation

Every point can connect to every other point.

The cost of an edge is:

|x1 - x2| + |y1 - y2|

This becomes a Minimum Spanning Tree problem.

Algorithm

  1. Start from any point.
  2. Add reachable points into min heap.
  3. Select minimum cost edge.
  4. Add unvisited point into MST.
  5. Continue until all points are connected.

Dry Run

Start Point

(0,0)

Add Closest Point

Cost = 4

Continue Expanding MST

4 + 3 + 4 + 9

Answer

 20

Approach : Prim's Algorithm

Treat every point as a graph node.

Use Manhattan Distance as edge weight.

Prim's Algorithm efficiently builds the MST while minimizing total cost.

Practice

Complexity Analysis

Time Complexity: O(n² log n)Explanation: For every selected point, distances to remaining points may be inserted into the priority queue. Heap operations take O(log n).

Space Complexity: O(n²)
Explanation: In the worst case, the priority queue can contain O(n²) candidate edges.

Why This Problem is Important

This problem teaches how Minimum Spanning Trees can be applied to geometric and coordinate-based problems.

Common Beginner Mistakes

  • Using Euclidean Distance instead of Manhattan Distance.
  • Forgetting visited checks.
  • Building incorrect edge costs.
  • Confusing MST with shortest path problems.

Interview Tip

Always mention:

Every point can connect to every other point, making this a complete graph. Prim's Algorithm efficiently finds the Minimum Spanning Tree.

Related Questions

  • Prim's Algorithm
  • Kruskal Algorithm
  • Network Delay Time
  • Path With Minimum Effort
  • Optimize Water Distribution in a Village

Final Takeaway

Min Cost to Connect All Points is a classic MST application where Manhattan Distance acts as edge weight. Recognizing the MST pattern quickly leads to an efficient Prim's Algorithm solution.