Watch 10 video solutions for Min Cost to Connect All Points, a medium level problem involving Array, Union Find, Graph. This walkthrough by NeetCode has 141,055 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.
Example 2:
Input: points = [[3,12],[-2,5],[-4,1]] Output: 18
Constraints:
1 <= points.length <= 1000-106 <= xi, yi <= 106(xi, yi) are distinct.Problem Overview: You are given n points on a 2D plane. The cost to connect two points equals their Manhattan distance |x1-x2| + |y1-y2|. The goal is to connect every point so that all points are reachable from each other while minimizing the total connection cost. This is a classic Minimum Spanning Tree (MST) problem on a complete graph where each pair of points forms an edge weighted by Manhattan distance.
Approach 1: Kruskal's Algorithm with Union-Find (Time: O(n^2 log n), Space: O(n^2))
Model the problem as a graph with n vertices. Since every pair of points can connect, generate all n(n-1)/2 edges and compute their Manhattan distances. Sort these edges by cost. Then iterate through the sorted list and use a Union-Find (Disjoint Set Union) structure to check whether two points already belong to the same component. If they do not, union them and add the edge cost to the total. Continue until n-1 edges are selected. This greedy strategy guarantees a valid MST because edges are processed from smallest weight to largest. This approach works well when you are comfortable managing edge lists and union operations using Union Find.
Approach 2: Prim's Algorithm (Time: O(n^2), Space: O(n))
Prim's algorithm builds the MST incrementally. Start from any point and mark it as visited. For every unvisited point, maintain the minimum cost required to connect it to the current MST. At each step, pick the unvisited point with the smallest connection cost, add it to the MST, and update distances for the remaining points. Because the graph is dense (every pair of points has an edge), computing distances on the fly avoids storing all edges. This leads to O(n^2) time and O(n) extra space. The approach relies heavily on greedy expansion and is often easier to implement for dense graph problems involving minimum spanning tree construction.
Recommended for interviews: Prim's algorithm is usually the expected solution. The graph is fully connected, so generating all edges for Kruskal introduces unnecessary overhead. Demonstrating Kruskal first shows you recognize the MST pattern, but implementing Prim with a distance array shows deeper understanding of how MST algorithms behave on dense graphs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kruskal's Algorithm with Union-Find | O(n^2 log n) | O(n^2) | When you want a straightforward MST approach using sorted edges and Disjoint Set Union. |
| Prim's Algorithm (Array-based) | O(n^2) | O(n) | Best for dense graphs like this one where every pair of nodes can connect. |