Min Cost to Connect All Points
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Points on a plane; connecting two costs their Manhattan distance. Return the minimum total cost to connect all points (any two reachable through the links).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you always add the cheapest link leaving the connected set, can you ever regret it?
- Hint 2Keep, for every outside point, the cheapest known link to the network.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Laying internet cable between houses. Start with any one house on the network. Then repeatedly ask: "which house still outside is cheapest to connect to the network?", connect it and pay that price. For each outside house you only need to remember the cheapest link to any connected house; whenever a new house joins, check whether it offers a cheaper link to the outside houses.
- The obvious way
Try all spanning trees: exponential.
- The key insight
cheapest[p] = cheapest link from p to the connected set (infinity at first, 0 for the start point). Repeat n times: pick the unconnected point with the smallest cheapest, connect it and add its cost to the total; then for every unconnected point update cheapest with the distance to the newly connected point. O(n²) which suits n up to 1000.
- The algorithm
- cheapest = infinity for all, 0 for point 0; total = 0.
- Pick the unconnected point with the smallest cheapest.
- Connect it: total + cheapest.
- Update every unconnected point's cheapest with its distance to this one. Repeat n times.
Watch it run
Examplepoints = [(0,0), (2,2), (3,10), (5,2), (7,0)]
Start with the house at (0,0), cost 0. The nearest outside house is (2,2) at distance 4. Connect it: total 4.
total = 4
Where people slip
- Distance is Manhattan: |x1 - x2| + |y1 - y2|, not straight-line.
- Kruskal with Union-Find also works; with ~1000 points Prim's O(n²) is simple.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def min_cost_connect_points(points):
count = len(points)
infinity = float("inf")
cheapest = [infinity] * count # cheapest link from each house to the network
cheapest[0] = 0
on_network = [False] * count
total = 0
for _ in range(count):
nearest = -1
for house in range(count):
if not on_network[house] and (nearest == -1 or cheapest[house] < cheapest[nearest]):
nearest = house
on_network[nearest] = True
total += cheapest[nearest]
for house in range(count):
if not on_network[house]:
distance = abs(points[nearest][0] - points[house][0]) + abs(points[nearest][1] - points[house][1])
cheapest[house] = min(cheapest[house], distance)
return totalNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.