117. Minimum Cost to Connect Points
You may connect any pair of points at a cost equal to their Manhattan distance: |x1 - x2| + |y1 - y2|. Select connections so every point can reach every other point while minimizing total connection cost.
Connections may be shared by many routes. Identical coordinates still represent separate input vertices, and an empty or single-point collection needs no connection cost.
Example 1
Input
[[0,0],[2,2],[3,10],[5,2],[7,0]]
Output
20
Explanation: One optimal tree uses edge costs 4,3,4,9. This is a sum of connecting edges, not a sum of distances from point zero.
Example 2
Input
[[1,1],[1,1],[2,1]]
Output
1
Explanation: Duplicate coordinates are distinct vertices connected at zero cost.
Example 3
Input
[[MIN,MIN],[MAX,MAX]]
Output
8589934590
Explanation: Both coordinate differences and their sum exceed int range.
Constraints
0 <= points.length <= 2000points[i].length == 2-231 <= points[i][j] <= 231 - 1
Hints
Hint 1
Why can an optimal connecting network be reduced to a spanning tree?
Hint 2
For each outside point, keep the cheapest edge into the growing tree.
Hint 3
Choose the minimum key, add it once, and update outside keys with one-edge Manhattan costs.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Each outside key tracks the cheapest edge into the current tree
[[0,0],[2,2],[3,10],[5,2],[7,0]]
20