Minimum Cost to Connect All Points

Given an array of points on a 2D plane, connect all points so that every point is reachable from every other point. The cost to connect two points is the Manhattan distance between them. Return the minimum total cost required to connect all points. Pattern focus: MST. Design a solution that works for dense point sets, avoids repeated pair processing, and handles boundary cases such as a single point.

Input Format

points = array of [x, y] coordinates

Output Format

minimum total cost to connect all points

Constraints

  • 1 <= points.length <= 10^4
  • -10^6 <= x, y <= 10^6
  • points are all distinct.

Examples

Example 1:

Input:

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

Output:

20

Explanation:

A minimum spanning connection uses four edges with total Manhattan cost 20.

Example 2:

Input:

points = [[3,12],[-2,5],[-4,1]]

Output:

18

Explanation:

The cheapest way to connect all three points has total cost 18.

Example 3:

Input:

points = [[7,7]]

Output:

0

Explanation:

A single point needs no edges, so the cost is 0.

Loading...
Minimum Cost to Connect All Points