Data Structures19 sections · 729 units
Open in Course

Problem - Min Cost to Connect Points

MST on points

Given an array of points where points[i]=[xi,yi]\text{points}[i] = [x_i, y_i], connect all points such that the total cost is minimized.

The cost of connecting two points is the Manhattan distance: xixj+yiyj|x_i - x_j| + |y_i - y_j|. Return the minimum cost to connect all points.

Example: points =[[0,0],[2,2],[3,10],[5,2],[7,0]]= [[0,0],[2,2],[3,10],[5,2],[7,0]] returns 2020. You're finding an MST where edge weights are Manhattan distances. Constraints: up to 10001000 points.