Min Cost to Connect All Points
Problem Description
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
- All pairs (xi, yi) are distinct.
Solve it on LeetCode
Approaches
1. Kruskal's Algorithm with Union-Find
Intuition:
The problem can be translated into finding a Minimum Spanning Tree (MST) of a graph where each point represents a node, and the edges are the Manhattan distance between each pair of points.
Kruskal’s Algorithm is a common approach to solve the MST problem. It sorts all the edges in increasing order of their weights and adds them one by one to the MST if they don’t form a cycle. To check cycles efficiently, we use a Union-Find data structure.
Code:
- Time Complexity: O(E log E + E α(V)), where E is the number of edges and V is the number of vertices. Sorting the edges takes O(E log E), and the union-find operations take O(E α(V)).
- Space Complexity: O(E + V), storing edges and union-find structures.
2. Prim's Algorithm using Priority Queue
Intuition:
Prim's Algorithm grows an MST from a single starting point by adding the cheapest edge to the set of connected points. We can implement this efficiently using a priority queue to always extend MST with the lowest weight edge available.
Code:
- Time Complexity: O(V^2 log V), where V is the number of vertices. Each vertex can potentially have an edge to all other vertices and each operation in priority queue is log V.
- Space Complexity: O(V), storing minimum distances and mark arrays.