Show problems as
Classic problem #1584MediumArrayUnion-FindGraph TheoryMinimum Spanning TreePrim's AlgorithmKruskal's AlgorithmBorůvka's Algorithm

Min Cost to Connect All Points

Real-world version: Trenching the Sprinkler Valves
Tracked in this browser only
Read Min Cost to Connect All Points on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMinimum Spanning Tree · Graphs, animated step by step

A groundskeeper is running irrigation pipe between the sprinkler valves sunk into a flat field. Valve i sits at points[i] = [x_i, y_i], measured in metres from the pump house. No two valves share a position.

Trenches may only follow the paving joints, which run strictly north-south or strictly east-west, so a trench laid straight between valve i and valve j swallows |east_i - east_j| + |north_i - north_j| metres of pipe. Any pair of valves may be trenched together.

Water flows from one valve to another whenever some chain of trenches links them. The groundskeeper wants every valve on one linked network. Return the smallest number of metres of pipe that a set of trenches achieving this can use.

Examples

Example 1

Input
points = [[3, 1], [7, 1], [5, 4], [1, 6]]
Output
15

Trenching valve 0 to valve 1 takes 4 metres, valve 0 to valve 2 takes 5, and valve 2 to valve 3 takes 6, which is 15 metres and leaves all four valves on one network.

Example 2

Input
points = [[0, 3], [3, 0], [0, -3], [-3, 0]]
Output
18

Running valve 0 to valve 1, valve 1 to valve 2 and valve 2 to valve 3 costs 6 metres each, for 18 metres, and every valve is reachable from every other.

Example 3

Input
points = [[0, 0]]
Output
0

The single valve is already a network on its own, so no trench is dug.

Example 4

Input
points = [[2, 2], [2, 5], [2, 9], [2, 14]]
Output
12

All four valves stand on the same paving joint. Linking each valve to the next one up the line costs 3 + 4 + 5 = 12 metres.

Constraints

  • 1 <= points.length <= 1000
  • points[i].length == 2
  • -10^6 <= east_i, north_i <= 10^6
  • All the positions points[i] are distinct.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_cost_connect_points(points: list[list[int]]) -> int:
Java
public int minCostConnectPoints(int[][] points)

More on the same topics