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. (0,0) to (2,2) with cost 4.
2. (2,2) to (5,2) with cost 3.
3. (5,2) to (7,0) with cost 5.
4. (7,0) to (3,10) with cost 14. Total minimum cost = 4 + 3 + 5 + 8 = 20

Example 2

Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

Steps

1. Calculate distances: Compute the Manhattan distance between all pairs of points.
2. Mininum Spanning Tree (MST): Use Prim's or Kruskal's algorithm to find the minimum spanning tree. This algorithm efficiently finds the minimum set of edges that connect all vertices (points) without forming cycles.
3. Sum of edge weights: The sum of the weights (distances) of the edges in the MST is the minimum cost to connect all points.

Explanation

This problem is a classic Minimum Spanning Tree (MST) problem. We need to find the cheapest way to connect all points such that there's a path between any two. A MST guarantees this. Prim's and Kruskal's algorithms are efficient ways to solve this. We'll use Prim's algorithm here for its relative simplicity in implementation.

Prim's Algorithm:

1. Start with an arbitrary point.
2. Repeatedly add the nearest unconnected point to the MST until all points are connected. The "nearest" is determined by the Manhattan distance.

Code

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;
    if (n <= 1) return 0;

    // Adjacency matrix to store distances.  Infinity represents no direct connection.
    const adjMatrix: number[][] = Array(n).fill(null).map(() => Array(n).fill(Infinity));

    // Calculate Manhattan distances
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            adjMatrix[i][j] = adjMatrix[j][i] = dist;
        }
    }

    // Prim's algorithm
    const minCost = 0;
    const visited: boolean[] = Array(n).fill(false);
    const minEdge: number[] = Array(n).fill(Infinity);
    minEdge[0] = 0; // Start from the first point.

    for (let i = 0; i < n; i++) {
        let minIndex = -1;
        for (let j = 0; j < n; j++) {
            if (!visited[j] && (minIndex === -1 || minEdge[j] < minEdge[minIndex])) {
                minIndex = j;
            }
        }

        if (minIndex !== -1) {
            minCost += minEdge[minIndex];
            visited[minIndex] = true;
            for (let j = 0; j < n; j++) {
                if (!visited[j] && adjMatrix[minIndex][j] < minEdge[j]) {
                    minEdge[j] = adjMatrix[minIndex][j];
                }
            }
        }
    }

    return minCost;
};

Complexity

• Time Complexity: O(N^2), where N is the number of points. This is dominated by the distance calculation and Prim's algorithm.
• Space Complexity: O(N^2) to store the adjacency matrix. Could be optimized to O(N) using a different data structure if you don't need to store all distances at once. However, the adjacency matrix makes Prim's algorithm easier to implement.