Loading problem...
You are given a collection of station locations on a two-dimensional grid, where each station is represented by its coordinates points[i] = [xᵢ, yᵢ].
Your goal is to construct a network that connects all stations together using the minimum total wiring cost. The cost of laying a wire between any two stations at coordinates [xᵢ, yᵢ] and [xⱼ, yⱼ] is computed as the taxicab distance between them: |xᵢ - xⱼ| + |yᵢ - yⱼ|, where |val| represents the absolute value of val.
Return the minimum total cost required to wire all stations together such that every station is reachable from every other station through the network. A valid network ensures that there exists exactly one simple path between any pair of stations (i.e., the network forms a tree structure with no cycles).
Note: The taxicab distance (also known as Manhattan distance or L1 distance) measures the distance between two points along axes at right angles, similar to how a taxi would navigate a city grid where it can only travel along streets.
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]20We can connect the stations optimally as follows: connect (0,0)-(2,2) with cost 4, connect (2,2)-(5,2) with cost 3, connect (5,2)-(7,0) with cost 4, and connect (2,2)-(3,10) with cost 9. Total minimum cost = 4 + 3 + 4 + 9 = 20. Notice that every station is reachable from every other station through exactly one path.
points = [[3,12],[-2,5],[-4,1]]18One optimal way is to connect (3,12) to (-2,5) with cost |3-(-2)| + |12-5| = 5 + 7 = 12, then connect (-2,5) to (-4,1) with cost |(-2)-(-4)| + |5-1| = 2 + 4 = 6. Total cost = 12 + 6 = 18.
points = [[0,0],[1,0],[0,1]]2Connect (0,0)-(1,0) with cost 1, and (0,0)-(0,1) with cost 1. All three stations are connected with a total cost of 2.
Constraints