All problems

Min Cost to Connect Points

Medium · minimum spanning tree

You are given the positions of n towers on a flat map as a list points, where points[i] = [x, y]. You want every tower to be linked to every other one, either directly or through a chain of other towers, by laying cables between pairs of towers.

A cable between two towers [x1, y1] and [x2, y2] costs |x1 - x2| + |y1 - y2|. Cables may be laid between any two towers you like, and you may lay as many or as few as you need.

Return the smallest total cost of cables that links all the towers together. If there is only one tower, nothing needs to be laid and the answer is 0.

Two towers may stand at the same position. A cable between them costs 0.

Examples

Example 1

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

Output: 20

Lay cables 0-1 (cost 4), 1-3 (cost 3), 3-4 (cost 4) and 1-2 (cost 9): 4 + 3 + 4 + 9 = 20.

Example 2

Input: points = [[1, 1], [4, 5]]

Output: 7

The only cable costs 3 + 4 = 7.

Example 3

Input: points = [[3, 3]]

Output: 0

A single tower needs no cable.

Constraints