1584. Min Cost to Connect All Points
Problem Description
In this problem, you are given an array points
, which contains several points representing coordinates on a 2D plane. Each point is provided as a pair [x_i, y_i]
. The objective is to find the minimum total cost to connect all these points together. The cost to connect any two points [x_i, y_i]
and [x_j, y_j]
is calculated using the Manhattan distance, which is the sum of the absolute differences of their coordinates: |x_i - x_j| + |y_i - y_j|
. The end result is that every point must be connected to all other points with exactly one simple path between any two points, meaning that there are no cycles and each pair of points is connected directly or indirectly.
Intuition
To solve this problem, we need to find the minimum cost to connect all points. This is a classic example of a Minimum Spanning Tree (MST) problem, which connects all vertices in a graph in such a way that the sum of the weights of the edges is as small as possible and there are no cycles.
The solution makes use of a graph-based algorithm known as Prim's algorithm. Here's the thought process:
- We start by transforming our 2D points into a graph where each point is a vertex, and the edge weight between any two vertices is their Manhattan distance.
- Initialize a list called
dist
which will keep the minimum distance to connect each point to our growing tree. Initially, all distances are set to infinity. - Choose any point to start with and update its distance in
dist
to 0 because we can start from it without any cost. - Now, for each of the points, we perform the following steps:
- Find the point with the minimum distance that has not been visited yet. This point is now considered part of the MST and its distance is added to the total cost
ans
. - Mark this point as visited.
- Update the distances of the remaining points. If any not-yet-visited point can be connected to our tree at a lesser cost than previously recorded, we update its distance in
dist
.
- Find the point with the minimum distance that has not been visited yet. This point is now considered part of the MST and its distance is added to the total cost
- After including all the points in our MST, the sum of the distances will give us the cost to connect all points with minimum total cost.
By leveraging Prim's algorithm, the solution gradually builds the MST by picking the nearest unvisited point at each step and ensures that the total cost is minimized.
Learn more about Union Find, Graph and Minimum Spanning Tree patterns.
Solution Approach
The implementation of the solution follows a series of systematic steps which adhere to Prim's Algorithm for finding the Minimum Spanning Tree (MST) in a weighted graph. Here's a closer look at how the code achieves this:
-
Creating the graph: We initialize a 2D list
g
(short for graph) with sizen x n
, wheren
is the number of points. Here,g[i][j]
will store the Manhattan distance between the i-th and j-th point. -
Initialization: We introduce an array
dist
and set all initial distances toinf
(infinity), implying that initially, all points are infinitely far away from the tree we're building. Avis
(visited) array is also used to keep track of the points that have been added to the MST. -
Priming the first point: We set the distance of the starting point (arbitrarily chosen to be the first point in our list) to 0, because the cost of including the first point in our MST is nothing.
-
Building the MST: We then enter a loop that will iterate
n
times, once for each point. Inside the loop, we implement the core logic of Prim's algorithm:- Finding the next point to add: We search through all points to find the one that is not yet visited and has the smallest distance in
dist
. We can add this point to the MST at the least cost. - Adding the point to MST and updating the cost: Mark this point as visited and add the distance to the total cost (
ans
), which accumulates the cost of connecting to the MST. - Updating distances: Lastly, we iterate over all other points to recalculate the minimum distance needed to connect them to the MST, updating our
dist
array. If the Manhattan distance from the newly added point to any other point is less than the currently known distance, we update the distance accordingly.
- Finding the next point to add: We search through all points to find the one that is not yet visited and has the smallest distance in
The solution utilizes the following algorithms, data structures, and patterns:
- Prim's Algorithm: For incrementally building the MST.
- Graph Representation: A 2D list stores the graph where edges represent the cost to connect points.
- Greedy Selection: At each step, we choose the smallest cost edge to add a non-MST vertex.
- Arrays for Distances and Visited: To track the minimum distances and whether a point has been added to MST.
By the end of the loop, ans
will contain the sum of the distances of all the edges in the MST, which is the minimum cost to connect all the points.
Throughout the code, efficiency comes from the fact that we only need to consider each potential edge once when we add a new vertex to the MST, rather than needing to traverse the entire graph each time.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the aforementioned solution approach to a small example. Consider the array of points points = [[0,0], [2,2], [3,10], [5,2], [7,0]]
. The goal is to connect these points so that the total cost, defined by the Manhattan distance, is minimized.
Step 1: Creating the graph
First, we create our graph g
with the Manhattan distances between each pair of points:
- Distance between points
[0,0]
and[2,2]
is|0-2| + |0-2| = 4
. - Distance between points
[0,0]
and[3,10]
is|0-3| + |0-10| = 13
. - (Similarly, we calculate distances between all pairs of points).
Thus, the graph g
will look like a matrix where g[i][j]
represents the distance between i-th
and j-th
points.
Step 2: Initialization
We initialize the dist
array to [inf, inf, inf, inf, inf]
where each entry corresponds to a point, signifying the initial cost of connecting it is infinity.
Step 3: Priming the first point
We choose the first point [0,0]
to start with and set dist[0]
to 0
.
Step 4: Building the MST
- First iteration: We find the point with the smallest distance in
dist
that hasn't been visited. This is[0,0]
. We mark it as visited.- We update
dist
based on the distances from[0,0]
to other points, resulting indist = [0, 4, 13, 7, 7]
.
- We update
- Second iteration: The next unvisited point with the smallest distance is
[2,2]
, with distance4
.- We add this distance to our total cost and mark
[2,2]
as visited. - Update
dist
to reflect the closest distances using[2,2]
. Newdist
values will bedist = [0, 4, 9, 3, 5]
(changed from[3,10]
and[5,2]
).
- We add this distance to our total cost and mark
- Third iteration: Now
[5,2]
has the smallestdist
of3
.- We add
3
to the total cost, mark[5,2]
as visited. - Update
dist
todist = [0, 4, 9, 3, 5]
(no changes this time since no other point offers a shorter distance).
- We add
- Fourth iteration: Point
[7,0]
has the smallestdist
of5
.- We add
5
to the total cost, mark[7,0]
as visited. - Update
dist
todist = [0, 4, 8, 3, 5]
(changed from[3,10]
).
- We add
- Fifth iteration: The only remaining point is
[3,10]
withdist
of8
.- We add
8
to our total cost and mark[3,10]
as visited.
- We add
Total cost to connect all points is now 0 + 4 + 3 + 5 + 8 = 20
.
At each step, we chose the edge with the minimum cost to add a new point to our growing MST, and we ensured this by updating distances for the remaining points whenever a new point was added to the MST.
By following these steps iteratively, and using updated distances to determine the next closest point, we were able to build a connection between all the points at a minimum cost using Prim's algorithm.
Solution Implementation
1class Solution:
2 def minCostConnectPoints(self, points: List[List[int]]) -> int:
3 # Number of points in the list
4 num_points = len(points)
5
6 # Graph represented as an adjacency matrix with initialized distances
7 graph = [[0] * num_points for _ in range(num_points)]
8
9 # Initialize all distances to infinity
10 distances = [float('inf')] * num_points
11
12 # Keep track of visited points to avoid cycles
13 visited = [False] * num_points
14
15 # Calculate the distances between all points and populate the graph
16 for i, (x1, y1) in enumerate(points):
17 for j in range(i + 1, num_points):
18 x2, y2 = points[j]
19 distance = abs(x1 - x2) + abs(y1 - y2)
20 graph[i][j] = graph[j][i] = distance
21
22 # Starting from point 0
23 distances[0] = 0
24
25 # Variable to store the minimum cost to connect all points
26 min_cost = 0
27
28 # Prim's algorithm to find the minimum spanning tree (MST)
29 for _ in range(num_points):
30 # Index for the next point to visit
31 next_index = -1
32
33 # Find the closest unvisited point
34 for j in range(num_points):
35 if not visited[j] and (next_index == -1 or distances[j] < distances[next_index]):
36 next_index = j
37
38 # Mark this point as visited
39 visited[next_index] = True
40
41 # Add the distance to the minimum cost
42 min_cost += distances[next_index]
43
44 # Update distances relative to the current point
45 for j in range(num_points):
46 if not visited[j]:
47 distances[j] = min(distances[j], graph[next_index][j])
48
49 # Return the total cost to connect all points
50 return min_cost
51
1import java.util.Arrays;
2
3public class Solution {
4
5 public int minCostConnectPoints(int[][] points) {
6 // Define a very large number for the initial distances
7 final int INFINITY = 1 << 30;
8
9 // Get the number of points
10 int numberOfPoints = points.length;
11
12 // Create a graph represented by an adjacency matrix
13 int[][] graph = new int[numberOfPoints][numberOfPoints];
14
15 // Calculate all the distances between each pair of points
16 for (int i = 0; i < numberOfPoints; ++i) {
17 int x1 = points[i][0], y1 = points[i][1];
18 for (int j = i + 1; j < numberOfPoints; ++j) {
19 int x2 = points[j][0], y2 = points[j][1];
20 int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);
21 graph[i][j] = distance;
22 graph[j][i] = distance;
23 }
24 }
25
26 // Create an array to store the minimum distance from the selected point to the MST
27 int[] minDistances = new int[numberOfPoints];
28
29 // Keep track of visited points
30 boolean[] visited = new boolean[numberOfPoints];
31
32 // Initialize distances with a very large number
33 Arrays.fill(minDistances, INFINITY);
34
35 // The distance of the first point from itself is zero
36 minDistances[0] = 0;
37
38 // Accumulate the minimum cost of connecting all points
39 int totalCost = 0;
40
41 // Build the Minimum Spanning Tree (MST) using Prim's algorithm
42 for (int i = 0; i < numberOfPoints; ++i) {
43 int nearestPoint = -1; // Index of the closest unvisited point
44
45 // Find the unvisited point with the minimum distance to the MST
46 for (int k = 0; k < numberOfPoints; ++k) {
47 if (!visited[k] && (nearestPoint == -1 || minDistances[k] < minDistances[nearestPoint])) {
48 nearestPoint = k;
49 }
50 }
51
52 // Include this nearest unvisited point to the MST
53 visited[nearestPoint] = true;
54
55 // Add its distance to the total cost
56 totalCost += minDistances[nearestPoint];
57
58 // Update the minDistances array with the new possible shorter distances
59 for (int k = 0; k < numberOfPoints; ++k) {
60 if (!visited[k]) {
61 minDistances[k] = Math.min(minDistances[k], graph[nearestPoint][k]);
62 }
63 }
64 }
65
66 // Return the total cost of connecting all the points
67 return totalCost;
68 }
69}
70
1#include <vector>
2#include <climits>
3#include <cstring>
4
5using namespace std;
6
7class Solution {
8public:
9 int minCostConnectPoints(vector<vector<int>>& points) {
10 // Get the number of points
11 int numPoints = points.size();
12
13 // Initialize the graph with distances between each pair of points
14 int graph[numPoints][numPoints];
15 for (int i = 0; i < numPoints; ++i) {
16 int x1 = points[i][0], y1 = points[i][1];
17 for (int j = i + 1; j < numPoints; ++j) {
18 int x2 = points[j][0], y2 = points[j][1];
19 int distance = abs(x1 - x2) + abs(y1 - y2);
20 graph[i][j] = distance;
21 graph[j][i] = distance; // Since the graph is undirected
22 }
23 }
24
25 // Initialize the minimum distance array with a high value
26 int minDist[numPoints];
27 memset(minDist, 0x3f, sizeof(minDist));
28
29 // Keep track of visited points
30 bool visited[numPoints];
31 memset(visited, false, sizeof(visited));
32
33 // Start from the first point
34 minDist[0] = 0;
35 int totalCost = 0;
36
37 // Repeat for all points
38 for (int i = 0; i < numPoints; ++i) {
39 int currentPoint = -1;
40 // Select the unvisited point with the smallest tentative distance
41 for (int k = 0; k < numPoints; ++k) {
42 if (!visited[k] && (currentPoint == -1 || minDist[k] < minDist[currentPoint])) {
43 currentPoint = k;
44 }
45 }
46
47 // Mark the point as visited
48 visited[currentPoint] = true;
49 // Add its distance to the total cost
50 totalCost += minDist[currentPoint];
51
52 // Update the tentative distance to the other points
53 for (int k = 0; k < numPoints; ++k) {
54 if (!visited[k]) {
55 minDist[k] = min(minDist[k], graph[currentPoint][k]);
56 }
57 }
58 }
59 return totalCost;
60 }
61};
62
1function minCostConnectPoints(points: number[][]): number {
2 // Number of points in the input.
3 const numPoints = points.length;
4
5 // Graph represented by a 2D array where g[i][j] will hold the cost to connect point i and point j.
6 const graph: number[][] = Array(numPoints)
7 .fill(0)
8 .map(() => Array(numPoints).fill(0));
9
10 // Distances array, initialized with a large number to represent infinity.
11 const minDistances: number[] = Array(numPoints).fill(Number.MAX_SAFE_INTEGER);
12
13 // Visited array to track whether a point has been included in the MST.
14 const visited: boolean[] = Array(numPoints).fill(false);
15
16 // Fill the graph with the Manhattan distances between all pairs of points.
17 for (let i = 0; i < numPoints; ++i) {
18 const [x1, y1] = points[i];
19 for (let j = i + 1; j < numPoints; ++j) {
20 const [x2, y2] = points[j];
21 const distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);
22 graph[i][j] = distance;
23 graph[j][i] = distance;
24 }
25 }
26
27 // Initialize the total cost of the minimum spanning tree (MST).
28 let totalCost = 0;
29 // Start with the first point.
30 minDistances[0] = 0;
31
32 // Iterate over all points to build the MST.
33 for (let i = 0; i < numPoints; ++i) {
34 let currentPoint = -1;
35
36 // Select the point with the minimum distance that has not been visited.
37 for (let k = 0; k < numPoints; ++k) {
38 if (!visited[k] && (currentPoint === -1 || minDistances[k] < minDistances[currentPoint])) {
39 currentPoint = k;
40 }
41 }
42
43 // Mark the selected point as visited.
44 visited[currentPoint] = true;
45 // Add its cost to the total cost of the MST.
46 totalCost += minDistances[currentPoint];
47
48 // Update the distances of the points adjacent to the selected point.
49 for (let k = 0; k < numPoints; ++k) {
50 if (!visited[k]) {
51 minDistances[k] = Math.min(minDistances[k], graph[currentPoint][k]);
52 }
53 }
54 }
55
56 // Return the total cost to connect all the points.
57 return totalCost;
58}
59
Time and Space Complexity
Time Complexity
The algorithm implemented in the given Python code resembles Prim's algorithm, which is a greedy algorithm for finding the minimum spanning tree of a graph. If we look at the nested loops and the operations inside them, the time complexity analysis is as follows:
- There is a double nested loop that initializes the graph
g
where each element represents the cost to connect two points. The initialization of this adjacency matrix runs inO(n^2)
time because it iterates through all pairs of points. - After initializing the graph, there is another loop that runs exactly
n
times wheren
is the number of points. - Inside this loop, there is another loop that selects the point with the minimum distance that hasn't been visited yet. This inner loop runs at most
n
times (in case all points have not been visited), resulting in a complexity ofO(n)
for this selection process. - After selecting the point with the minimum distance, another loop updates the distances of the remaining points. In the worst case, this loop runs
n
times for each of then
iterations of the outer loop.
The two dominant factors in the time complexity are the initialization of the graph O(n^2)
and the two nested loops inside the main loop O(n^2)
. Therefore, adding these two together gives us O(n^2) + O(n^2) = O(n^2)
which simplifies to O(n^2)
.
Space Complexity
As for the space complexity:
- The adjacency matrix
g
has a size ofn x n
, which gives a space complexity ofO(n^2)
. - The
dist
list and thevis
list each have a size ofn
, contributingO(n)
space each. - The other variables (
n
,i
,ans
, and the loop index variables) are of constant size and do not depend onn
.
Therefore, the overall space complexity of the algorithm is dominated by the adjacency matrix g
, which is O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Minimum Spanning Tree Forests The Umbristan Department of Forestry UDF is tackling a rather difficult problem and the Umbristan government has assigned you as one of its best workers to go resolve the issue When you arrive you are quickly briefed on the problem at hand Inside the Umbristan National Park there exists an