LeetEye LeetEye
Hard Advanced Graphs ~5 min

Min Cost to Connect All Points

advanced-graphs min-cost-to-connect-all-points

Problem

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Examples

Example 1
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Key Insight

This is classic MST: connect all nodes with minimum total edge weight.

MST problem: Prim's (grow tree greedily from one node) or Kruskal's (add smallest edges that don't form cycles). Both give minimum total edge weight.

How to Approach This Problem

Pattern Recognition: When you see keywords like min cost to connect all points advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 A Minimum Spanning Tree:
Answer: All of the above
MST has n-1 edges, minimum total weight, and no cycles.
2 For dense graphs (many edges), prefer:
Answer: Prim's with min-heap
Kruskal's sorts all edges O(E log E). Prim's processes O(V) nodes with heap.

Solution

import heapq

def minCostConnectPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 1:
        return 0
    
    # Prim's algorithm
    visited = set()
    min_heap = [(0, 0)]  # (cost, point_index)
    total_cost = 0
    
    while len(visited) < n:
        cost, i = heapq.heappop(min_heap)
        
        if i in visited:
            continue
        
        visited.add(i)
        total_cost += cost
        
        # Add edges to all unvisited points
        for j in range(n):
            if j not in visited:
                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                heapq.heappush(min_heap, (dist, j))
    
    return total_cost

Complexity Analysis

Time O(n² log n)
Space O(n²)

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye