Skip to content
BASA DSA

Min Cost to Connect All Points

MediumAdvanced Graphs

Connect all supplied points using edges costing Manhattan distance, abs(dx)+abs(dy). Return the minimum total cost of a connected network.

Example 1

Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree. Vertices: node 0: (0,0), node 1: (2,0), node 2: (2,3). Edges: node 0 ((0,0)) — node 1 ((2,0)) (2); node 0 ((0,0)) — node 2 ((2,3)) (5); node 1 ((2,0)) — node 2 ((2,3)) (3).253(0,0)(2,0)(2,3)
Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.

Input
points = [[0,0],[2,0],[2,3]]
Output
5

Explanation

Connect [0,0] to [2,0] for 2 and [2,0] to [2,3] for 3, totaling 5.

Example 2

Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree. Vertices: node 0: (5,-2). Edges: none.(5,-2)
Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.

Input
points = [[5,-2]]
Output
0

Explanation

One point already forms a connected network with no edge cost.

Example 3

Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree. Vertices: node 0: (-1,0), node 1: (1,0), node 2: (0,2). Edges: node 0 ((-1,0)) — node 1 ((1,0)) (2); node 0 ((-1,0)) — node 2 ((0,2)) (3); node 1 ((1,0)) — node 2 ((0,2)) (3).233(-1,0)(1,0)(0,2)
Input points in coordinate order. All candidate connections are shown, weighted by Manhattan distance; choose a minimum spanning tree.

Input
points = [[-1,0],[1,0],[0,2]]
Output
5

Explanation

Connect the horizontal points for 2 and attach [0,2] for 3, totaling 5.

Constraints

  • 1 <= number of distinct points <= 1000
  • Coordinates are -1000000..1000000

Function contractminCostConnectPointsArguments: json
Loading draft…
SolutionRuns on your device