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.
This approach involves treating the points as nodes of a graph and the Manhattan distance between them as the edge weights. The problem translates to finding a Minimum Spanning Tree (MST), which connects all nodes with the minimum edge weight.
Kruskal's algorithm is a popular choice for this kind of problem. It works as follows:
This approach efficiently computes the minimum cost of connecting all points.
This implementation first constructs all the edges with their distances, using a nested loop to calculate the Manhattan distance between each pair of points. Then, it sorts the edges by distance. The Union-Find structure is initialized and used to progressively add edges to the Minimum Spanning Tree as long as they connect previously disconnected components. The function returns the total cost of the spanning tree.
The time complexity is dominated by the sorting step and the union-find operations. Sorting takes O(E log E), where E is the number of edges. Union-Find operations are nearly constant time, resulting in an overall complexity of O(E log E). The space complexity is O(n) for the Union-Find structure and edge storage, where n is the number of points.
Another approach uses Prim's algorithm to construct the Minimum Spanning Tree (MST). Rather than sorting edges, Prim's method grows the MST one vertex at a time, starting from an arbitrary vertex and adding the minimum cost edge that expands the MST.
The steps involved are:
This approach offers a clear alternative to Kruskal's, particularly well-suited to densely connected systems.
This C version uses an array to track visited nodes and another to store the minimum weight edge for each node, initialized to infinity. The central loop iterates over all nodes, expanding the MST by connecting the node with the minimum edge weight. It updates the minimum weights for reachable unvisited nodes at each step.
This approach has a time complexity of O(n^2) due to nested loops over nodes, suitable for problems where n is moderately sized. Space complexity is O(n) for extra arrays managing node state and weights.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Kruskal's Algorithm with Union-Find | The time complexity is dominated by the sorting step and the union-find operations. Sorting takes |
| Approach 2: Prim's Algorithm | This approach has a time complexity of |
| Default Approach | — |
| 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. |
Prim's Algorithm - Minimum Spanning Tree - Min Cost to Connect all Points - Leetcode 1584 - Python • NeetCode • 141,055 views views
Watch 9 more video solutions →Practice Min Cost to Connect All Points with our built-in code editor and test cases.
Practice on FleetCode