A minimum spanning tree connects every node using the cheapest possible total edge weight. Two greedy algorithms find it: Kruskal (sort all edges, add each one that does not create a cycle) and Prim (grow one tree, always adding the cheapest edge leaving it).
You are given a list points of integer coordinates [x, y]. The cost of connecting two points is their Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost to make all points connected (there must be exactly one simple path between any two points).
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
Constraints
1 <= len(points) <= 200, all points distinct- Target: O(n^2 log n) time (there are O(n^2) candidate edges)
Goals
- Recognise a minimum spanning tree problem from the phrase 'connect everything as cheaply as possible'
- Implement Kruskal's algorithm (sort edges, union-find) or Prim's algorithm (heap of frontier edges)
- Generate the implicit complete graph from a list of points