Sponsored
Sponsored
This approach involves treating the points as nodes of a graph and the Manhattan distance between them as the edge weights. The problem translates to finding a Minimum Spanning Tree (MST), which connects all nodes with the minimum edge weight.
Kruskal's algorithm is a popular choice for this kind of problem. It works as follows:
This approach efficiently computes the minimum cost of connecting all points.
The time complexity is dominated by the sorting step and the union-find operations. Sorting takes O(E log E), where E is the number of edges. Union-Find operations are nearly constant time, resulting in an overall complexity of O(E log E). The space complexity is O(n) for the Union-Find structure and edge storage, where n is the number of points.
1import java.util.*;
2
3class Solution {
4 static class Edge implements Comparable<Edge
The Java implementation uses an inner class to represent edges with the necessary fields point1, point2, and weight. Edges are sorted by weight using Java's Collections.sort to facilitate Kruskal's algorithm. The Union-Find structure is used to ensure that connecting an edge results in adding a new connection to the resulting Minimum Spanning Tree without forming cycles, and it returns the minimum cost of connecting all points.
Another approach uses Prim's algorithm to construct the Minimum Spanning Tree (MST). Rather than sorting edges, Prim's method grows the MST one vertex at a time, starting from an arbitrary vertex and adding the minimum cost edge that expands the MST.
The steps involved are:
This approach offers a clear alternative to Kruskal's, particularly well-suited to densely connected systems.
This approach has a time complexity of O(n^2) due to nested loops over nodes, suitable for problems where n is moderately sized. Space complexity is O(n) for extra arrays managing node state and weights.
1#include <vector>
2#include <unordered_set>
3#include <queue>
4#include <utility>
5#include <functional>
6#include <cmath>
7using namespace std;
8
9class Solution {
10public:
11 int minCostConnectPoints(vector<vector<int>>& points) {
12 int n = points.size();
13 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
14 vector<int> minDist(n, INT_MAX);
15 vector<bool> inMST(n, false);
16 int totalCost = 0;
17 minDist[0] = 0;
18 pq.push({0, 0}); // {dist, point}
19
20 while (!pq.empty()) {
21 auto [dist, curr] = pq.top();
22 pq.pop();
23
24 if (inMST[curr]) continue;
25 inMST[curr] = true;
26 totalCost += dist;
27
28 for (int next = 0; next < n; ++next) {
29 if (!inMST[next]) {
30 int nextDist = abs(points[curr][0] - points[next][0]) + abs(points[curr][1] - points[next][1]);
31 if (nextDist < minDist[next]) {
32 minDist[next] = nextDist;
33 pq.push({nextDist, next});
34 }
35 }
36 }
37 }
38
39 return totalCost;
40 }
41};The C++ solution efficiently grows the MST using a priority queue and a distance array. The main loop examines each unvisited node, invoking the priority queue to always select the minimum weight edge. As nodes are assimilated into the MST, edges to their neighbors are recalculated and stored in the priority queue for subsequent choices.