# Min Cost to Connect All Points
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/min-cost-to-connect-all-points)
Canonical: https://scaleengineer.com/dsa/problems/min-cost-to-connect-all-points
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find), [Minimum Spanning Tree](https://scaleengineer.com/algorithms/minimum-spanning-tree)
**Data structures:** Array, Graph
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Directi](https://scaleengineer.com/companies/directi)
---
## 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|`, where `|val|` denotes the absolute value of `val`.

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

**Example 1:**

![](https://assets.glich.co/dsa/min-cost-to-connect-all-points/image0.png) 

**Input:** points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
**Output:** 20
**Explanation:** 
![](https://assets.glich.co/dsa/min-cost-to-connect-all-points/image1.png)
We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

**Example 2:**

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

**Constraints:**

* `1 <= points.length <= 1000`
* `-106 <= xi, yi <= 106`
* All pairs `(xi, yi)` are distinct.

# Approaches
## Kruskal's Algorithm with Union-Find
This approach models the problem as finding a Minimum Spanning Tree (MST) in a complete graph. The points are treated as vertices, and the weight of an edge between any two points is their Manhattan distance. Kruskal's algorithm is a classic method for finding an MST. It works by sorting all possible edges by weight and adding them to the MST one by one, as long as they don't form a cycle.
**Time:** O(N^2 log N) - The number of edges `E` is O(N^2). Calculating all edge weights takes O(N^2). The dominant step is sorting these `E` edges, which takes O(E log E) = O(N^2 log(N^2)) = O(N^2 log N). The Union-Find operations for all edges take O(E * α(N)), where α is the very slow-growing inverse Ackermann function, making it nearly constant time per operation. This is overshadowed by the sorting time. · **Space:** O(N^2) - We need to create and store a list of all possible edges between the N points. Since the graph is complete, there are O(N^2) edges. The Union-Find data structure requires an additional O(N) space.
**Pros:** It's a direct and conceptually clear application of a well-known MST algorithm.; The logic is relatively easy to follow if you are familiar with Kruskal's algorithm and Union-Find.
**Cons:** High space complexity due to the need to store all possible edges.; Slower than the optimized Prim's algorithm for dense graphs, which is the case in this problem.
### Explanation
The core idea is to generate all possible connections (edges) between the points and then select the cheapest ones to form a tree that connects all points without cycles. 

1.  **Edge Generation**: First, we compute the Manhattan distance between every pair of points. For `N` points, this results in `N * (N - 1) / 2` edges. We store these edges, typically as a list of objects or tuples containing the two points and the distance.

2.  **Sorting**: We sort the list of all edges in non-decreasing order of their weights (distances).

3.  **MST Construction**: We use a Union-Find data structure to build the MST. This structure is initialized with each point in its own separate set. We then iterate through our sorted list of edges. For each edge, we check if its two endpoints are already in the same set. If they are not, adding the edge won't create a cycle. So, we add its weight to our total cost and merge the two sets using the `union` operation. We continue this process until we have added `N - 1` edges, which is the number of edges in an MST for `N` vertices.

```java
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n <= 1) {
            return 0;
        }

        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new Edge(i, j, dist));
            }
        }

        Collections.sort(edges, (a, b) -> a.weight - b.weight);

        UnionFind uf = new UnionFind(n);
        int minCost = 0;
        int edgesUsed = 0;

        for (Edge edge : edges) {
            if (uf.union(edge.u, edge.v)) {
                minCost += edge.weight;
                edgesUsed++;
                if (edgesUsed == n - 1) {
                    break;
                }
            }
        }
        return minCost;
    }

    class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        boolean union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
                return true;
            }
            return false;
        }
    }
}
```
### Algorithm
- Create a list of all `N*(N-1)/2` edges. Each edge connects a pair of points, and its weight is their Manhattan distance.
- Sort this list of edges by weight in ascending order.
- Initialize a Union-Find (also known as Disjoint Set Union or DSU) data structure with `N` components, one for each point.
- Initialize `total_cost = 0` and `edge_count = 0`.
- Iterate through the sorted edges `(u, v)` with weight `w`:
  - If points `u` and `v` are not already in the same component (checked using the `find` operation):
    - Add the edge to the Minimum Spanning Tree (MST) by merging the components of `u` and `v` (using the `union` operation).
    - Add the edge's weight to the `total_cost`.
    - Increment `edge_count`.
  - Stop when `edge_count` reaches `N-1`, as the MST is complete.
- Return `total_cost`.

## Prim's Algorithm (Optimized for Dense Graphs)
This approach also solves the problem by finding a Minimum Spanning Tree (MST), but it uses Prim's algorithm. Prim's algorithm builds the MST by starting with an arbitrary vertex and iteratively adding the cheapest edge that connects a vertex in the MST to a vertex outside the MST. For a dense graph, where every vertex is connected to every other vertex, a specific implementation of Prim's that doesn't rely on a priority queue is highly efficient.
**Time:** O(N^2) - The main `while` loop runs `N` times to add each point to the MST. Inside this loop, we iterate through all `N` points to find the next vertex to add (O(N) operation). We then iterate through all `N` points again to update the `minCost` array (another O(N) operation). This results in a total time complexity of O(N * (N + N)) = O(N^2). · **Space:** O(N) - We use two arrays, `visited` and `minCost`, both of size N, to keep track of the state during the algorithm's execution.
**Pros:** More efficient in both time and space compared to the Kruskal's approach for this dense graph problem.; Optimal time complexity for a dense graph.; Excellent space complexity, using only linear extra space.
**Cons:** For very sparse graphs (which is not the case here), a priority-queue-based Prim's or Kruskal's algorithm could be more efficient.
### Explanation
This optimized version of Prim's algorithm is tailored for dense graphs. Instead of generating all edges upfront or using a complex data structure like a priority queue, it iteratively builds the MST by maintaining an array of minimum connection costs.

1.  **Initialization**: We use two arrays: `min_cost` of size `N` and `visited` of size `N`. `min_cost[i]` will hold the minimum cost to connect point `i` to the current set of points in the MST. We initialize `min_cost` with infinity for all points and `visited` with false. We pick a starting point (e.g., index 0) and set its `min_cost` to 0.

2.  **Iterative Growth**: The algorithm runs for `N` iterations. In each iteration:
    a. We find the unvisited point `u` with the smallest `min_cost`. This is the next point to be added to our MST.
    b. We add `min_cost[u]` to our `total_cost` and mark `u` as visited.
    c. We then update the costs for all other unvisited points. For each unvisited point `v`, we calculate the distance from our newly added point `u` to `v`. If this distance is less than the current `min_cost[v]`, we update `min_cost[v]`.

After `N` iterations, all points are part of the MST, and we have the minimum total cost.

```java
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n <= 1) {
            return 0;
        }

        boolean[] visited = new boolean[n];
        int[] minCost = new int[n];
        java.util.Arrays.fill(minCost, Integer.MAX_VALUE);

        minCost[0] = 0;
        int totalCost = 0;
        int numEdges = 0;

        while (numEdges < n) {
            int currMinEdge = Integer.MAX_VALUE;
            int currNode = -1;

            // Find the unvisited node with the smallest edge cost to the MST
            for (int i = 0; i < n; i++) {
                if (!visited[i] && minCost[i] < currMinEdge) {
                    currMinEdge = minCost[i];
                    currNode = i;
                }
            }

            totalCost += currMinEdge;
            visited[currNode] = true;
            numEdges++;

            // Update costs for its neighbors
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    int dist = Math.abs(points[currNode][0] - points[i][0]) + 
                               Math.abs(points[currNode][1] - points[i][1]);
                    minCost[i] = Math.min(minCost[i], dist);
                }
            }
        }

        return totalCost;
    }
}
```
### Algorithm
- Initialize an array `min_cost` of size `N` to store the minimum cost to connect each point to the growing MST. Fill it with infinity.
- Initialize a boolean array `visited` of size `N` to `false`.
- Initialize `total_cost = 0`.
- Choose an arbitrary start point (e.g., index 0) and set its `min_cost` to 0.
- Repeat `N` times:
  - Select an unvisited point `u` that has the minimum `min_cost` among all unvisited points.
  - Mark `u` as visited.
  - Add `min_cost[u]` to `total_cost`.
  - For every other point `v`:
    - If `v` is not visited, calculate the Manhattan distance `d` between `u` and `v`.
    - Update `min_cost[v]` if `d` is smaller: `min_cost[v] = min(min_cost[v], d)`.
- Return `total_cost`.

# Solutions
### Java

```java
class Solution {
public
  int minCostConnectPoints(int[][] points) {
    final int inf = 1 << 30;
    int n = points.length;
    int[][] g = new int[n][n];
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        int t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
        g[i][j] = t;
        g[j][i] = t;
      }
    }
    int[] dist = new int[n];
    boolean[] vis = new boolean[n];
    Arrays.fill(dist, inf);
    dist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int j = -1;
      for (int k = 0; k < n; ++k) {
        if (!vis[k] && (j == -1 || dist[k] < dist[j])) {
          j = k;
        }
      }
      vis[j] = true;
      ans += dist[j];
      for (int k = 0; k < n; ++k) {
        if (!vis[k]) {
          dist[k] = Math.min(dist[k], g[j][k]);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCostConnectPoints(vector<vector<int>> &points) {
    int n = points.size();
    int g[n][n];
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        int t = abs(x1 - x2) + abs(y1 - y2);
        g[i][j] = t;
        g[j][i] = t;
      }
    }
    int dist[n];
    bool vis[n];
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int j = -1;
      for (int k = 0; k < n; ++k) {
        if (!vis[k] && (j == -1 || dist[k] < dist[j])) {
          j = k;
        }
      }
      vis[j] = true;
      ans += dist[j];
      for (int k = 0; k < n; ++k) {
        if (!vis[k]) {
          dist[k] = min(dist[k], g[j][k]);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int: n = len(points) g = [[0] * n for _ in range(n)] dist = [inf] * n vis = [False] * 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 dist[0] = 0 ans = 0 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 vis[i] = True ans += dist[i] for j in range(n): if not vis[j]: dist[j] = min(dist[j], g[i][j]) return ans

```