Problem Description

You have a collection of points on a 2D coordinate plane. Each point is represented by its [x, y] coordinates. Your task is to connect all these points together with the minimum total cost.

The cost to connect any two points is calculated using the Manhattan distance formula:

• For points [x₁, y₁] and [x₂, y₂], the cost = |x₁ - x₂| + |y₁ - y₂|

The goal is to find the minimum total cost to create a connected network where:

• Every point is reachable from every other point
• There is exactly one simple path between any two points (forming a tree structure)

For example, if you have points [0,0], [2,2], and [3,10]:

• Cost between [0,0] and [2,2] = |0-2| + |0-2| = 4
• Cost between [2,2] and [3,10] = |2-3| + |2-10| = 9
• Cost between [0,0] and [3,10] = |0-3| + |0-10| = 13

You would connect them in a way that minimizes the total cost while ensuring all points remain connected.

The solution uses Prim's algorithm to find the Minimum Spanning Tree (MST):

1. First, it builds a complete graph where edge weights are Manhattan distances between all pairs of points
2. Starting from point 0, it greedily adds the nearest unvisited point to the growing tree
3. The dist array tracks the minimum distance from each point to the current tree
4. The algorithm continues until all points are connected

The total cost is the sum of all edges in the minimum spanning tree.

Intuition

When we need to connect all points with minimum cost, we're essentially looking for a Minimum Spanning Tree (MST) problem. Think of it like building a road network between cities - we want every city to be reachable, but we want to minimize the total road construction cost.

The key insight is that we need exactly n-1 edges to connect n points (this forms a tree). Adding any more edges would create cycles and increase cost unnecessarily. We want to select these n-1 edges such that their total weight is minimized.

Since we can potentially connect any point to any other point (complete graph), we have many choices. The greedy approach works here: always pick the cheapest available connection that adds a new point to our growing network.

Prim's algorithm is perfect for this scenario because:

1. We start with one point and grow our connected component one point at a time
2. At each step, we look at all possible edges from our current connected points to unconnected points
3. We pick the cheapest edge that connects to a new point

The dist array is the clever part - instead of checking all edges every time, we maintain the minimum distance from each unvisited point to our current tree. When we add a new point to our tree, we only need to update distances based on that single point's connections.

Why does this greedy approach work? Because once a point is connected to our tree through its cheapest available edge, we never need to reconsider it. The MST property guarantees that selecting the minimum weight edge at each step that doesn't create a cycle will give us the global minimum.

The Manhattan distance calculation |x₁ - x₂| + |y₁ - y₂| is just how we measure the "cost" between points - it's given by the problem and represents the edge weights in our graph.

Learn more about Union Find, Graph and Minimum Spanning Tree patterns.

Solution Approach

The implementation uses Prim's algorithm to find the Minimum Spanning Tree. Let's walk through the code step by step:

1. Graph Construction:

g = [[0] * n for _ in range(n)]
for i, (x1, y1) in enumerate(points):
    for j in range(i + 1, n):
        x2, y2 = points[j]
        t = abs(x1 - x2) + abs(y1 - y2)
        g[i][j] = g[j][i] = t

We build an adjacency matrix g where g[i][j] stores the Manhattan distance between point i and point j. Since the graph is undirected, we set both g[i][j] and g[j][i] to the same value.

2. Initialize Data Structures:

dist = [inf] * n
vis = [False] * n
dist[0] = 0
ans = 0

• dist[i]: Minimum distance from point i to the current MST
• vis[i]: Boolean flag indicating if point i is already in the MST
• We start from point 0 by setting dist[0] = 0
• ans accumulates the total cost

3. Main Prim's Loop:

for _ in range(n):
    i = -1
    for j in range(n):
        if not vis[j] and (i == -1 or dist[j] < dist[i]):
            i = j

For each of the n iterations:

• Find the unvisited point with minimum distance to the current MST
• This is a linear search through all points to find the minimum

4. Add Point to MST:

vis[i] = True
ans += dist[i]

Mark the selected point as visited and add its connection cost to the total.

5. Update Distances:

for j in range(n):
    if not vis[j]:
        dist[j] = min(dist[j], g[i][j])

After adding point i to the MST, update the minimum distances for all unvisited points. If the distance from the newly added point i to point j is less than the current minimum distance to j, update it.

Time Complexity: O(n²) where n is the number of points

• Building the graph: O(n²)
• Main loop runs n times, each iteration takes O(n) for finding minimum and updating distances

Space Complexity: O(n²) for storing the adjacency matrix

The algorithm guarantees we find the minimum cost to connect all points because Prim's algorithm always produces an optimal MST by greedily selecting the minimum weight edge at each step.

Example Walkthrough

Let's walk through a small example with 4 points: [[0,0], [2,2], [3,10], [5,2]]

Step 1: Build the adjacency matrix with Manhattan distances

Calculate distances between all pairs:

• Points 0→1: |0-2| + |0-2| = 4
• Points 0→2: |0-3| + |0-10| = 13
• Points 0→3: |0-5| + |0-2| = 7
• Points 1→2: |2-3| + |2-10| = 9
• Points 1→3: |2-5| + |2-2| = 3
• Points 2→3: |3-5| + |10-2| = 10

Adjacency matrix:

     0   1   2   3
0 [  0   4  13   7 ]
1 [  4   0   9   3 ]
2 [ 13   9   0  10 ]
3 [  7   3  10   0 ]

Step 2: Initialize Prim's algorithm

• dist = [0, inf, inf, inf] (start from point 0)
• vis = [False, False, False, False]
• ans = 0

Iteration 1:

• Find unvisited point with minimum dist: Point 0 (dist=0)
• Mark point 0 as visited: vis = [True, False, False, False]
• Add to total cost: ans = 0
• Update distances from point 0:
  • dist[1] = min(inf, 4) = 4
  • dist[2] = min(inf, 13) = 13
  • dist[3] = min(inf, 7) = 7
• New state: dist = [0, 4, 13, 7]

Iteration 2:

• Find unvisited point with minimum dist: Point 1 (dist=4)
• Mark point 1 as visited: vis = [True, True, False, False]
• Add to total cost: ans = 4
• Update distances from point 1:
  • dist[2] = min(13, 9) = 9
  • dist[3] = min(7, 3) = 3
• New state: dist = [0, 4, 9, 3]

Iteration 3:

• Find unvisited point with minimum dist: Point 3 (dist=3)
• Mark point 3 as visited: vis = [True, True, False, True]
• Add to total cost: ans = 7
• Update distances from point 3:
  • dist[2] = min(9, 10) = 9
• New state: dist = [0, 4, 9, 3]

Iteration 4:

• Find unvisited point with minimum dist: Point 2 (dist=9)
• Mark point 2 as visited: vis = [True, True, True, True]
• Add to total cost: ans = 16
• All points visited

Result: The minimum cost to connect all points is 16. The MST edges are:

• Point 0 → Point 1 (cost 4)
• Point 1 → Point 3 (cost 3)
• Point 1 → Point 2 (cost 9)

This creates a tree where all points are connected with minimum total cost.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of three main parts:

1. Building the adjacency matrix: The nested loops iterate through all pairs of points to calculate Manhattan distances, which takes O(n²) time.

2. Prim's algorithm implementation:

   • The outer loop runs n times
   • For each iteration, finding the minimum distance unvisited vertex takes O(n) time
   • Updating distances to neighbors also takes O(n) time
   • Total for Prim's algorithm: O(n) × (O(n) + O(n)) = O(n²)

Overall time complexity: O(n²) + O(n²) = O(n²)

Space Complexity: O(n²)

The space usage includes:

• Adjacency matrix g: O(n²) space for storing all edge weights
• Distance array dist: O(n) space
• Visited array vis: O(n) space

Overall space complexity: O(n²) + O(n) + O(n) = O(n²)

The dominant factor is the adjacency matrix storing the complete graph representation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Priority Queue Without Edge Relaxation Optimization

A common mistake is implementing Prim's algorithm with a priority queue (heap) but still checking all edges for every node, leading to inefficient time complexity.

Problematic Approach:

import heapq

def minCostConnectPoints(points):
    n = len(points)
    # Build complete graph (still O(n²) edges)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((cost, i, j))
  
    # Using heap but still processing all O(n²) edges
    heapq.heapify(edges)
    # ... rest of implementation

This approach doesn't improve the overall complexity because we're still dealing with all O(n²) edges upfront.

Better Solution:

import heapq

def minCostConnectPoints(points):
    n = len(points)
    visited = [False] * n
    min_heap = [(0, 0)]  # (cost, point_index)
    total_cost = 0
    edges_used = 0
  
    while min_heap and edges_used < n:
        cost, u = heapq.heappop(min_heap)
      
        if visited[u]:
            continue
          
        visited[u] = True
        total_cost += cost
        edges_used += 1
      
        # Only compute distances when needed
        for v in range(n):
            if not visited[v]:
                distance = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                heapq.heappush(min_heap, (distance, v))
  
    return total_cost

2. Integer Overflow in Distance Calculation

When dealing with large coordinate values, the Manhattan distance calculation might overflow in languages with fixed integer sizes.

Problematic Code:

# If points have very large coordinates close to INT_MAX
distance = abs(x1 - x2) + abs(y1 - y2)  # Might overflow in other languages

Solution: In Python, this isn't an issue due to arbitrary precision integers, but be aware when porting to other languages. Consider using long/int64 types or checking for overflow conditions.

3. Forgetting to Handle Edge Cases

Common Edge Cases Often Missed:

• Single point (n = 1): Should return 0
• Two points (n = 2): Should return their Manhattan distance
• Duplicate points: Manhattan distance would be 0

Robust Solution:

def minCostConnectPoints(points):
    n = len(points)
  
    # Handle edge cases
    if n <= 1:
        return 0
    if n == 2:
        return abs(points[0][0] - points[1][0]) + abs(points[0][1] - points[1][1])
  
    # Continue with main algorithm...

4. Inefficient Distance Recalculation

Calculating Manhattan distance multiple times for the same pair of points wastes computation.

Inefficient Pattern:

# Recalculating distance every time we need it
for _ in range(n):
    for j in range(n):
        if not visited[j]:
            # Recalculating distance here
            dist = abs(points[current][0] - points[j][0]) + abs(points[current][1] - points[j][1])

Solution: Pre-compute and store distances in an adjacency matrix (as shown in the original solution) or use memoization if memory is a concern.

5. Using Kruskal's Algorithm with Poor Union-Find Implementation

Some developers choose Kruskal's algorithm but implement Union-Find without path compression or union by rank, resulting in poor performance.

Poor Union-Find:

def find(parent, i):
    if parent[i] != i:
        return find(parent, parent[i])  # No path compression
    return i

def union(parent, x, y):
    parent[find(parent, x)] = find(parent, y)  # No union by rank

Optimized Union-Find:

def find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])  # Path compression
    return parent[i]

def union(parent, rank, x, y):
    px, py = find(parent, x), find(parent, y)
    if px == py:
        return False
    # Union by rank
    if rank[px] < rank[py]:
        parent[px] = py
    elif rank[px] > rank[py]:
        parent[py] = px
    else:
        parent[py] = px
        rank[px] += 1
    return True