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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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 |
Prim's Algorithm - Minimum Spanning Tree - Min Cost to Connect all Points - Leetcode 1584 - Python • NeetCode • 115,027 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 FleetCodePractice this problem
Open in Editor