Min Cost To Connect All Points

Back to problems

Leetcode

Medium

Arrays

Graphs

Greedy

Minimum Spanning Tree

Min Cost To Connect All Points

Connect every point with minimum total Manhattan distance.

Acceptance 0%

Start Practice

Problem Statement

You are given a list of points on a 2D grid. Each point is represented by its integer coordinates [x, y].

You may connect any two points with an edge whose cost is their Manhattan distance:

$|x_1 - x_2| + |y_1 - y_2|$

Your task is to connect all points so that every point is reachable from every other point, while minimizing the total cost of the chosen connections.

In other words, build a connected network spanning all points with the smallest possible sum of edge costs.

Input Format

An array of points points, where points[i] = [x_i, y_i].
Each point is a 2D coordinate with integer values.

Output Format

Return the minimum total cost required to connect all points.

Constraints

All points are distinct.
The network must connect every point directly or indirectly.
The cost of an edge is the Manhattan distance between its endpoints.

Examples

Sample cases returned by the problem API.

Example 1

Input

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

Output

Explanation

One optimal way is to connect the points with edges of costs 4, 3, 4, and 9, for a total of 20.

Example 2

Input

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

Output

Explanation

The minimum spanning network can be formed by connecting the closest pairs with total cost 18.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress