⚡Flashcard Drill➔
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

  1. This is a minimum spanning tree on a complete graph with Manhattan edge weights.
  2. Prim's algorithm fits well: grow the tree one node at a time, always adding the cheapest connection.
  3. A min-heap of (cost, node) holds the candidate edges from the tree to the outside.
  4. 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 seen check 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems