Min Cost to Connect All Points
The key idea
The points form a complete weighted graph where edge weight is the Manhattan distance. Connecting all points at minimum total cost is exactly a Minimum Spanning Tree. Grow the tree greedily: repeatedly add the cheapest edge that reaches a point not yet in the tree (Prim's).
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.
Constraints
- 1 <= points.length <= 1000
- -10^6 <= xi, yi <= 10^6
- All pairs (xi, yi) are distinct.
Examples
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18
Complexity
Time: O(n^2) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Graph problems
- Cheapest Flights Within K StopsMEDIUM
- Clone GraphMEDIUM
- Course Schedule IVMEDIUM
- Evaluate DivisionMEDIUM
- Find the Town JudgeEASY
- Minimum Height TreesMEDIUM
- Network Delay TimeMEDIUM
- Number of ProvincesMEDIUM
- Path With Minimum EffortMEDIUM
- Reconstruct ItineraryHARD
- Swim in Rising WaterHARD