NeetCode #630LC-1584MediumAdvanced GraphsNC 150NC 250
← Back to All Problems#630 · #1584 · Min Cost to Connect All Points(连接所有点的最小费用)
📌 Problem Statement & Constraints
You are given an array of
points on a 2D plane. Return the minimum cost to connect all points, where the cost between two points is their Manhattan distance. Constraints: 1 <= points.length <= 1000, -10^6 <= x, y <= 10^6.💡 Core Algorithmic Approaches
- This is a minimum spanning tree on a complete graph with Manhattan edge weights.
- Prim's algorithm fits well: grow the tree one node at a time, always adding the cheapest connection.
- A min-heap of
(cost, node)holds the candidate edges from the tree to the outside. - The graph is complete, so the edge count is O(n^2), but Prim only needs O(n) heap operations with lazy deletion.
💻 Benchmark Python3 Implementation
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
import heapq
n = len(points)
seen = [False] * n
h = [(0, 0)] # (cost, node)
total = 0
used = 0
while h and used < n:
d, i = heapq.heappop(h)
if seen[i]:
continue # already in the tree
seen[i] = True
total += d
used += 1
for j in range(n):
if not seen[j]:
cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
heapq.heappush(h, (cost, j))
return total⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log n): O(n) heap operations per added node.
💾 Space Complexity
O(n^2) for the heap in the worst case.
⚠️ Interview Pitfalls & Follow-ups
- Using Kruskal with all O(n^2) edges sorted: also correct but uses O(n^2) memory for the edge list.
- Forgetting the
seencheck on pop: the same node could be added twice. - Using Euclidean distance: the cost is Manhattan.
- Assuming the graph is disconnected: it is complete, so an MST always exists.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.