0412MediumArrayUnion-FindGraph TheoryMinimum Spanning TreePrim's AlgorithmKruskal's AlgorithmBorůvka's Algorithm

Trenching the Sprinkler Valves

Tracked in this browser only

Trains the technique from

LeetCode 1584Min Cost to Connect All Points

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_cost_connect_points(points: list[list[int]]) -> int:

Java

public int minCostConnectPoints(int[][] points)

The intended approach

Time O(n^2) for n valves: n rounds, each scanning the outside valves twice.Space O(n) for the per-valve stored length and the inside flags.

Grow one network outward from valve 0. Alongside it keep, for every valve still outside the network, the length of the shortest trench that would attach it to something already inside. Each round takes the valve whose stored length is smallest, charges that length, marks it inside, and then walks the remaining valves once to lower any stored length that the newly attached valve beats. The dense sweep avoids ever materialising the pair list.

Pythonentry point: min_cost_connect_points

def min_cost_connect_points(points):
    # Prim on the dense graph: every valve pair is joinable, so keep one
    # "cheapest pipe reaching this valve from the built network" number per
    # valve and refresh it each time a valve joins the network.
    n = len(points)
    if n < 2:
        return 0
    INF = float("inf")
    best = [INF] * n
    inside = [False] * n
    best[0] = 0
    total = 0
    for _ in range(n):
        pick = -1
        for i in range(n):
            if not inside[i] and (pick < 0 or best[i] < best[pick]):
                pick = i
        inside[pick] = True
        total += best[pick]
        px, py = points[pick]
        for j in range(n):
            if not inside[j]:
                d = abs(points[j][0] - px) + abs(points[j][1] - py)
                if d < best[j]:
                    best[j] = d
    return total

The obvious version

Materialise all n*(n-1)/2 trench lengths, sort them, and walk them in order, keeping a trench whenever a disjoint-set structure says its two valves are not linked yet. O(n^2 log n).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost_connect_points(points):
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((d, i, j))
    edges.sort()
    root = list(range(n))

    def find(a):
        while root[a] != a:
            root[a] = root[root[a]]
            a = root[a]
        return a

    total = 0
    used = 0
    for d, i, j in edges:
        ri, rj = find(i), find(j)
        if ri != rj:
            root[ri] = rj
            total += d
            used += 1
            if used == n - 1:
                break
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in