Asked at

Min Cost To Connect All Points

Medium
VerifiedMSTGreedyUnion Find~25 min

You have points as a number[][] where each entry is [x, y]. The cost to connect two points is the Manhattan distance |x1 - x2| + |y1 - y2|.

Return the minimum total cost to connect every point, so any point is reachable from any other through the chosen connections.

The input arrives as a single number[][].

Examples

in[[0,0],[2,2],[3,10],[5,2],[7,0]]
out20

A minimum spanning tree over Manhattan distances costs 20.

in[[3,12],[-2,5],[-4,1]]
out18

Connecting all three points costs 18.

Constraints

  • 1 ≤ points.length ≤ 1000
  • -10⁶ ≤ x, y ≤ 10⁶
  • All points are distinct.
  • Cost between two points is their Manhattan distance.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.