noodleProblems/
Min Cost to Connect All Points
#152

Min Cost to Connect All Points

AlgorithmmediumArrayUnion FindGraph

You are given points, an array of distinct points on a 2-D plane where points[i] = [xi, yi].

The cost of connecting two points is the **Manhattan distance** between them: |xi - xj| + |yi - yj|.

Return the **minimum total cost** to connect *all* the points so that there is exactly one path between any two of them. (In graph terms: the weight of a minimum spanning tree over the points.)

Example cases

  • five points
    in points =
    00
    22
    310
    52
    70
    out 20
    Connecting (0,0)-(2,2)=4, (2,2)-(5,2)=3, (5,2)-(7,0)=4, (5,2)-(3,10)=... the minimum spanning tree totals 20.
  • three points in a line
    in points =
    312
    -25
    -41
    out 18
    (-4,1)-(-2,5)=6 and (-2,5)-(3,12)=12 spans all three for 18.
  • single point
    in points =
    00
    out 0

Constraints

  • 1 <= points.length <= 1000
  • -10^6 <= xi, yi <= 10^6
  • All pairs (xi, yi) are distinct.
Saved
points =
[[0,0],[2,2],[3,10],[5,2],[7,0]]