Cheapest Point Wiring

Medium

Points points lie on a plane, where points[i] = [x, y] are integer coordinates. A wire between two points costs their Manhattan distance: |x₁ − x₂| + |y₁ − y₂|. Lay wires so that every point can be reached from every other point. Return the minimum total cost of the wires.

Example 1

points=[[0, 0], [3, 1], [3, 5], [-2, 0]] → 10

Run wires (0,0)–(−2,0) for 2, (0,0)–(3,1) for 4 and (3,1)–(3,5) for 4. Total: 10.

Example 2

points=[[7, -7]] → 0

There is only one point, so nothing needs wiring.

Example 3

points=[[1, 1], [4, 2], [2, 6]] → 10

Constraints

1 ≤ len(points) ≤ 1000
-10⁶ ≤ x, y ≤ 10⁶
All points are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Union Find Graph Array Minimum Spanning Tree

Similar problems

Ratio Chain Queries Medium Consistent Letter Equations Medium The Cheapest Road Network Medium Rooms Open from the Hall Medium Groups Linked by Shared Tags Medium

Input

points=[[0, 0], [3, 1], [3, 5], [-2, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.