Connect Planar Points at Minimum Manhattan Cost

### Problem Each entry of `points` is an integer coordinate pair. An edge between two points costs the sum of their horizontal and vertical distances. Select edges so every pair of points has exactly one simple path between them. Return the minimum total cost. ```cpp class Solution { public: int minCostConnectPoints(vector<vector<int>>& points); }; ``` ### Examples **Example 1:** ```text points = [[0,0],[0,3],[2,3]] Output: 5 Explanation: Use costs 3 and 2; the remaining possible edge costs 5. ``` **Example 2:** ```text points = [[-2,1],[1,1],[1,5],[4,5]] Output: 10 Explanation: Consecutive listed points can be joined with costs 3, 4, and 3. The two cost-3 pairs require a connection of at least 4 between them. ``` ### Constraints - `1 <= points.length <= 1000`. - Each coordinate lies in `[-10^6,10^6]`. - Coordinate pairs are distinct. ### Clarifying Questions Exactly one simple path means the selected graph is a tree. Return its cost; an optimal tree itself need not be unique. ```hint Inspect the structure What must hold about connectivity, simple paths, and total cost in a valid optimal selection? ``` ### Reasoning checkpoints - Show that the selected connections give exactly one simple path between every pair of points. - Justify the minimum cost under Manhattan distances and explain resource use for up to 1000 points. ### Optional extensions What time and space trade-offs arise from materializing all pairwise connection costs before finding the minimum total connection cost?