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.
1var minCostConnectPoints = function(points) {
2 const n = points.length;
3 const edges = [];
JavaScript handles its edge list as an array of arrays, each entry containing the two points and their weight. Sorting them based on weight ensures that the algorithm uses Kruskal's approach to add the smallest edges possible while keeping track of connected components through union-find operations. The resulting minimum connection cost across the points is returned.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MinCostConnectPoints(int[][] points) {
6 int n = points.Length;
7 int[] minDist = new int[n];
8 bool[] inMST = new bool[n];
9 PriorityQueue<(int, int), int> pq = new();
10 Array.Fill(minDist, int.MaxValue);
11 minDist[0] = 0;
12 pq.Enqueue((0, 0), 0);
13
14 int totalCost = 0;
15
16 while (pq.TryDequeue(out var edge, out int cost)) {
17 int u = edge.Item2;
18 if (inMST[u]) continue;
19
20 inMST[u] = true;
21 totalCost += cost;
22
23 for (int v = 0; v < n; v++) {
24 if (!inMST[v]) {
25 int dist = Math.Abs(points[u][0] - points[v][0]) + Math.Abs(points[u][1] - points[v][1]);
26 if (dist < minDist[v]) {
27 minDist[v] = dist;
28 pq.Enqueue((dist, v), dist);
29 }
30 }
31 }
32 }
33
34 return totalCost;
35 }
36}The C# solution keeps true to Prim's principles, leveraging queues to always approach the least weight edge. The functional syntax ensures that executing step requires efficient calculation, updating, and checking to extend the MST with the minimal increase in cost. It successfully returns the minimum spanning connection cost for the given points.