Loading problem…
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the Manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Example 1
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: Connect (0,0)-(2,2) for 4, (2,2)-(5,2) for 3, (5,2)-(7,0) for 4 and (2,2)-(3,10) for 9. These four links connect every point for a total cost of 20, the cheapest possible.
Example 2
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Explanation: The pairwise costs are 12 between (3,12) and (-2,5), 6 between (-2,5) and (-4,1), and 18 between (3,12) and (-4,1). The two cheapest links, 6 + 12 = 18, connect all three points.
Example 3
Input: points = [[0,0],[1,1],[1,0],[0,1]]
Output: 3
Explanation: The four corners of a unit square can be connected with three sides, each costing 1, for a total of 3.
Prim's algorithm grows a tree one vertex at a time, always reaching out to the cheapest neighbour available. Because every pair of points has an edge in this problem, we don't need a heap of edges — a flat array `min_dist[v]` tracking the cheapest distance from the current tree to each outsider is enough. With `n ≤ 1000` the dense `O(n²)` form is faster than the heap-based one because it avoids logarithmic overhead.
Run checks all cases above. Submit evaluates all test cases.