Link the Outposts

MediumAdvanced Graphs

Problem

Research outposts sit on a city grid at points[i] = [x, y]. Roads can only run along the grid, so linking outposts i and j costs their Manhattan distance |xi - xj| + |yi - yj|.

Return the minimum total cost to link all outposts so that every outpost can reach every other one.

Example 1

Input:
points = [[0,0],[1,4],[5,1],[6,6]]
Output:
17

Link 0–1 (5), 0–2 (6) and 2–3 (6).

Example 2

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

Example 3

Input:
points = [[-1,-1],[1,1]]
Output:
4

Constraints

  • 1 ≤ points.length ≤ 1000
  • -10^6 ≤ x, y ≤ 10^6
  • All points are distinct.

Hint

Show the first hint

This is a minimum spanning tree on a complete graph. How many edges does it have?

Walkthrough

How to approach it

01Clarify before coding

  • Is the distance Manhattan or Euclidean? Manhattan: |dx| + |dy|.
  • Can points repeat? No, all points are distinct.
  • One outpost? Nothing to link: cost 0.

02Brute force

Build all n(n-1)/2 edges and run Kruskal.

Cost: O(n² log n) time and O(n²) memory: about 500,000 edges to store and sort for n = 1000. Correct but heavier than needed.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.