Min Cost to Connect All Points medium

Problem Statement

You are given an array points where points[i] = [xi, yi] represents the coordinates of the ith point on a 2D plane. The cost of connecting two points points[i] and points[j] is the Manhattan distance between them: |xi - xj| + |yi - yj|.

Return the minimum cost to connect all points such that there is a path between any two points.

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as follows:

1. Connect (0,0) and (2,2) with cost 4.
2. Connect (2,2) and (5,2) with cost 3.
3. Connect (5,2) and (7,0) with cost 5.
4. Connect (7,0) and (3,10) with cost 14. Total minimum cost = 4 + 3 + 5 + 8 = 20

Example 2

Input: points = [[3,12],[-2,5],[10,10],[10,-2],[4,11]] Output: 39

Steps

1. Calculate distances: Compute the Manhattan distance between all pairs of points. This forms a complete graph where edges are weighted by the distances.

2. Minimum Spanning Tree (MST): Find the Minimum Spanning Tree (MST) of this complete graph. The MST connects all points with the minimum total edge weight. Prim's algorithm or Kruskal's algorithm are efficient ways to find the MST.

3. Return total cost: The total weight of the edges in the MST is the minimum cost to connect all points.

Explanation

The problem is equivalent to finding a Minimum Spanning Tree (MST) in a complete graph where nodes are the points and edge weights are the Manhattan distances. Both Prim's and Kruskal's algorithms are suitable for solving this. We'll use Prim's algorithm in the solution below for its relative simplicity in implementation.

Prim's Algorithm:

• Start with a single node in the MST.
• Iteratively add the nearest node (minimum edge weight) that is not yet in the MST. This step uses a priority queue (min-heap) for efficiency.
• Continue until all nodes are in the MST.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int MinCostConnectPoints(int[][] points) {
        int n = points.Length;
        if (n <= 1) return 0;

        // Calculate distances (adjacency matrix)
        long[,] dist = new long[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long d = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
                dist[i, j] = dist[j, i] = d;
            }
        }

        // Prim's Algorithm
        long minCost = 0;
        bool[] visited = new bool[n];
        long[] minEdge = new long[n];
        Array.Fill(minEdge, long.MaxValue);
        minEdge[0] = 0;

        for (int count = 0; count < n; count++) {
            long min = long.MaxValue;
            int u = -1;

            for (int v = 0; v < n; v++) {
                if (!visited[v] && minEdge[v] < min) {
                    min = minEdge[v];
                    u = v;
                }
            }

            if (u == -1) break; // Should not happen in a connected graph
            visited[u] = true;
            minCost += min;

            for (int v = 0; v < n; v++) {
                if (!visited[v] && dist[u, v] < minEdge[v]) {
                    minEdge[v] = dist[u, v];
                }
            }
        }

        return (int)minCost;
    }
}

Complexity

• Time Complexity: O(N^2 log N), dominated by Prim's algorithm with a min-heap (priority queue). Building the distance matrix takes O(N^2).
• Space Complexity: O(N), mainly for the visited array and minEdge array. The adjacency matrix uses O(N^2) but this could be optimized using adjacency list if memory becomes a concern for extremely large inputs.