Problem Explanation

The problem is to compute the minimum total cost to connect all points in a 2-dimensional space. The input to the problem is a list of points, where each point is represented by a pair of integers. The cost of connecting two points is defined as the Manhattan distance between them, which is the sum of the distances between their x-coordinates and their y-coordinates. Therefore, to solve this problem, we must find the ordering to connect points that minimizes the total sum of the Manhattan distances.

An example will demonstrate how to solve this problem. Suppose the points are [[0,0],[2,2],[3,10],[5,2],[7,0]]. The optimal way to connect these points would be to connect them in the order they appear. This will give us a cost of 2 (from [0,0] to [2,2]) + 8 (from [2,2] to [3,10]) + 8 (from [3,10] to [5,2]) + 2 (from [5,2] to [7,0])= 20. This is the minimum total cost of connecting all the points.

Approach

The approach to this problem is to use a variant of the Prim's algorithm. Starting from the initial point, connect it to the point with minimum distance. Then, for each remaining unvisited point, we update its shortest distance if it can be visited in a shorter distance. We repeat the process until all points are visited. The total minimum cost will be the sum of these minimum distances.

Here is how the algorithm works with an example.

Suppose we are given points = [[0,0],[2,2],[3,10],[5,2],[7,0]].

• Start with the first point [0,0] and calculate the distance to the rest of the points (2, 10, 7, 9).

• Choose the nearest point with minimum distance (2 in this case). Add the minimum distance to the total cost (total cost becomes 2).

• Repeat the process from the point [2,2]. The remaining distances are (8, 5, 7). The minimum distance is 5. Add it to the total cost (total cost becomes 2 + 5 = 7).

• Continue this process until all points are visited. The total cost at the end of the process (20 in this case) will be the minimum cost.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minCostConnectPoints(vector<vector<int>>& points) {
6        int n = points.size(), res = 0, cur = 0;
7        vector<int> dist(n, INT_MAX), seen(n);
8        dist[0] = 0;
9        for (int i = 0; i < n; ++i) {
10            int mini = INT_MAX, idx;
11            for (int j = 0; j < n; ++j) {
12                if (!seen[j] && dist[j] < mini) {
13                    mini = dist[j];
14                    idx = j;
15                }
16            }
17            cur = idx;
18            seen[cur] = 1;
19            res += dist[cur];
20            for (int j = 0; j < n; ++j) {
21                int newDist = abs(points[cur][0] - points[j][0]) + abs(points[cur][1] - points[j][1]);
22                if (!seen[j] && newDist < dist[j]) {
23                    dist[j] = newDist;
24                }
25            }
26        }
27        return res;
28    }
29};

Java Solution

1
2java
3class Solution {
4    public int minCostConnectPoints(int[][] points) {
5        int n = points.length, res = 0, cur = 0;
6        int[] dist = new int[n];
7        boolean[] seen = new boolean[n];
8        Arrays.fill(dist, Integer.MAX_VALUE);
9        dist[0] = 0;
10        for (int i = 0; i < n; ++i) {
11            int minDist = Integer.MAX_VALUE, idx = -1;
12            for (int j = 0; j < n; ++j) {
13                if (!seen[j] && dist[j] < minDist) {
14                    minDist = dist[j];
15                    idx = j;
16                }
17            }
18            cur = idx;
19            seen[cur] = true;
20            res += dist[cur];
21            for (int j = 0; j < n; ++j) {
22                int newDist = Math.abs(points[cur][0] - points[j][0]) + Math.abs(points[cur][1] - points[j][1]);
23                if (!seen[j] && newDist < dist[j]) {
24                    dist[j] = newDist;
25                }
26            }
27        }
28        return res;
29    }
30}

Python Solution

1
2python
3class Solution:
4    def minCostConnectPoints(self, points: List[List[int]]) -> int:
5        dist = lambda i, j: abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
6        n = len(points)
7        res = sum_ = float('inf')
8        curr = [0]
9        vis = [0] * n
10        vis[0] = 1
11        for _ in range(n - 1):
12            nxt_i, nxt_j, min_d = 0, 0, float('inf')
13            for i in curr:
14                for j in range(n):
15                    if not vis[j]:
16                        d = dist(i, j)
17                        if d < min_d:
18                            min_d = d
19                            nxt_i, nxt_j = i, j
20            curr = [nxt_j]
21            vis[nxt_j] = 1
22            res = min(res, sum_ += min_d)
23        return res

JavaScript Solution

1
2javascript
3var minCostConnectPoints = function(points) {
4    const n = points.length;
5    const dist = new Array(n).fill(Infinity);
6    const visited = new Array(n).fill(false);
7    let res = 0;
8    dist[0] = 0;
9    for(let i = 0; i < n; i++) {
10        let u = -1;
11        for(let j = 0; j < n; j++) {
12            if(!visited[j] && (u == -1 || dist[j] < dist[u])) {
13                u = j;
14            }
15        }
16        visited[u] = true;
17        res += dist[u];
18        for(let v = 0; v < n; v++) {
19            dist[v] = Math.min(dist[v], Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]));
20        }
21    }
22    return res;
23};

C# Solution

1
2csharp
3public class Solution {
4    public int MinCostConnectPoints(int[][] points) {
5        var n = points.Length;
6        var dist = new int[n];
7        var seen = new bool[n];
8        for (int i = 0; i < n; i++)
9            dist[i] = int.MaxValue;
10        dist[0] = 0;
11        var sum = 0;
12        for (int i = 0; i < n; i++) {
13            var minDist = int.MaxValue;
14            var minPoint = -1;
15            for (int j = 0; j < n; j++) {
16                if (!seen[j] && dist[j] < minDist) {
17                    minDist = dist[j];
18                    minPoint = j;
19                }
20            }
21            seen[minPoint] = true;
22            sum += minDist;
23            for (int j = 0; j < n; j++) {
24                var newDist = Math.Abs(points[minPoint][0] - points[j][0]) + Math.Abs(points[minPoint][1] - points[j][1]);
25                dist[j] = Math.Min(dist[j], newDist);
26            }
27        }
28        return sum;
29    }
30}

In each solution, we use a boolean array seen to keep track of points that have already been visited, and an integer array dist to store the minimum distance from the current vertex to every other vertex. The solution is built upon the idea of greedy algorithm and iterative process.Let's discuss the time complexity of each of the solutions.

For the C++ Solution, Java Solution and C# Solution, each iteration we select a point v taking O(n) time. In each selection, we update the distance of the remaining points to v taking O(n) time as well. Since we do this for each point, the time complexity is O(n^2).

Similarly, for Python solution, the outer loop and the inner loop both run n times, leading to a time complexity of O(n^2).

Lastly for the JavaScript Solution, first, we select the initial point with the smallest distance in O(n) time. Then for each remaining point, we update its distance. This update operation takes O(n). Therefore, in the worst scenario, we select and update the distances for all the n points. This results in a time complexity of O(n^2).

Approach Optimizations

If you want to optimize your approach for larger inputs, it would be possible with use of a priority queue data structure. Priority queue can help in reducing the time complexity of selecting the next point with minimum distance.

While this would increase the complexity of your code, it can be worth it for very large inputs as the time complexity would reduce from O(n^2) to O(n log n).

Let's wrap up this blog by mentioning that despite the complexity, the provided problem is a classic combinatorial optimization problem that occurs in many real-world settings and its solution demonstrates the power of greedy algorithms.