Min Cost to Connect All Points
You are given an array points of n points on a plane, where points[i] = [x, y]. The cost of connecting two points [x1, y1] and [x2, y2] is their Manhattan distance, |x1 - x2| + |y1 - y2|.
Return the minimum total cost to connect all the points, so that there is exactly one simple path (no loops) between any two points, that is, they form a tree. All the points are different.
Examples
Input points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
Output 20
Input points = [[3, 12], [-2, 5], [-4, 1]]
Output 18
Input points = [[0, 0]]
Output 0
One point needs no segments.
Constraints
- 1 <= points.length <= 1,000
- -1,000,000 <= x, y <= 1,000,000
- all the points are different
Stuck? Take one hint at a time
Common mistakes
- Building a minimum path (shortest path) instead of a tree: the cheapest way to join everything is not the sum of shortest paths from one point.
- Using Kruskal without a union find, and so adding segments that close loops.
- In Prim, updating dist for points already in the tree, or starting dist[0] at infinity so the first point is charged a cost.
- Counting each pair twice when listing the segments, which doubles the work for no benefit.
- Adding the placeholder for infinity to a distance in a fixed width integer, which overflows. Compare against the placeholder, never add to it.
Questions an interviewer may ask next
- The points are on a line (one dimension). What is the answer, and what simpler algorithm does it need? (Sort the points and add the gaps.)
- Some points are already connected for free. How do you start Prim or Kruskal? (Pre-merge those groups, or start with dist 0.)
- The cost is the straight line (Euclidean) distance. Which parts of the code change, and what do you watch for with floating point numbers?
- There are 100,000 points. Even Prim at n squared is too slow. What can you use? (Geometry: the minimum spanning tree uses only edges of a Delaunay triangulation for Euclidean distance.)
points
[[0,0],[2,2],[3,10],[5,2],[7,0]]
Expected output
20
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.