Min Cost to Connect All Points

Medium · Advanced Graphs

You are given a list of points on a 2D plane, each given as [x, y] coordinates. The cost of directly linking any two points equals the Manhattan distance between them (absolute difference in x plus absolute difference in y). Choose a set of links so that every point is connected to every other point, directly or through a chain of links, while minimizing the total cost of the links used. Return that minimum total cost.

Examples

Input:  points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Why:    Linking the points using minimum Manhattan-distance edges to span all five points gives a total cost of 20.

Input:  points = [[3,12],[-2,5],[-4,1]]
Output: 18
Why:    The cheapest way to join all three points uses the two shortest Manhattan-distance edges, totalling 18.

Input:  points = [[0,0]]
Output: 0
Why:    A single point needs no connections so the cost is zero.

Constraints

1 <= points.length <= 1000, points[i].length == 2, -10^6 <= xi, yi <= 10^6

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Min Cost to Connect All Points

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Min Cost to Connect All Points. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.