You get an array points of n points on a grid. Each point is written as [x, y].
Choose links between the points so that every point can reach every other point through them. Return the smallest total cost of these links.
A link can join any two points. A link between [x1, y1] and [x2, y2] costs |x1 - x2| + |y1 - y2|. This is their Manhattan distance. It is how far a taxi drives between them in a city of square blocks.
Example 1:
Input: points = [[1, 1], [4, 2], [2, 6], [7, 5]]
Output: 16
Explanation: Three links join the four points:
[1, 1] - [4, 2] costs 3 + 1 = 4,
[1, 1] - [2, 6] costs 1 + 5 = 6,
[4, 2] - [7, 5] costs 3 + 3 = 6.
In total, 4 + 6 + 6 = 16.
Other links also cost 6, so other choices give 16 too.
None costs less.
Example 2:
Input: points = [[-3, 2]] Output: 0 Explanation: There is only one point, so no link is needed.
Example 3:
Input: points = [[-2, -3], [0, 4], [3, -1]]
Output: 15
Explanation: There are three possible links:
[-2, -3] - [3, -1] costs 5 + 2 = 7,
[3, -1] - [0, 4] costs 3 + 5 = 8,
[-2, -3] - [0, 4] costs 2 + 7 = 9.
The two cheapest already join all three points.
Together they cost 7 + 8 = 15.
Constraints:
- 1 to 1,000 points.
- No two points are the same.
- Each coordinate is from -1,000,000 to 1,000,000.
Note:
Your algorithm should run in O(n2 log n) time and use O(n2) extra space.
The tutorial uses Kruskal's algorithm. Think of every pair of points as an edge of a graph. The edge's cost is the two points' Manhattan distance. There are n · (n - 1) / 2 edges. The cheapest way to connect all the points is a minimum spanning tree. It is n - 1 edges that connect every point, with the least total cost. Kruskal's algorithm sorts the edges from the cheapest up. It takes each edge whose two ends are still in different groups. That joins the two groups into one. An edge whose ends are already in the same group would only close a cycle. So it is skipped. Union-find tells in almost constant time whether two points are in the same group. The lesson Number of Connected Components in an Undirected Graph uses it too. After n - 1 edges every point is in one group, and the algorithm can stop.
Taking the cheapest edge between two groups is always safe. The finished tree has to join those two groups somehow. Say it used a dearer edge there. Swapping in the cheaper one would give a tree that costs no more. Sorting the n2 edges takes O(n2 log n) time. Keeping them takes O(n2) space.
Prim's algorithm is the other classic way. It grows a single tree from one point. Each time, it adds the cheapest edge from the tree to a point outside it. It can find that edge with a heap, as in Dijkstra's algorithm. This graph has an edge for every pair. On such a graph, a plain O(n2) scan works too.
Free plan: 30 tutor messages. PRO is unlimited.
