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:

  1. 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.
  2. 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.
  3. Choose any point to start with and update its distance in dist to 0 because we can start from it without any cost.
  4. 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.
  5. 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:

  1. Creating the graph: We initialize a 2D list g (short for graph) with size n x n, where n is the number of points. Here, g[i][j] will store the Manhattan distance between the i-th and j-th point.

  2. Initialization: We introduce an array dist and set all initial distances to inf (infinity), implying that initially, all points are infinitely far away from the tree we're building. A vis (visited) array is also used to keep track of the points that have been added to the MST.

  3. 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.

  4. 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.

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 Evaluator

Example 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 in dist = [0, 4, 13, 7, 7].
  • Second iteration: The next unvisited point with the smallest distance is [2,2], with distance 4.
    • We add this distance to our total cost and mark [2,2] as visited.
    • Update dist to reflect the closest distances using [2,2]. New dist values will be dist = [0, 4, 9, 3, 5] (changed from [3,10] and [5,2]).
  • Third iteration: Now [5,2] has the smallest dist of 3.
    • We add 3 to the total cost, mark [5,2] as visited.
    • Update dist to dist = [0, 4, 9, 3, 5] (no changes this time since no other point offers a shorter distance).
  • Fourth iteration: Point [7,0] has the smallest dist of 5.
    • We add 5 to the total cost, mark [7,0] as visited.
    • Update dist to dist = [0, 4, 8, 3, 5] (changed from [3,10]).
  • Fifth iteration: The only remaining point is [3,10] with dist of 8.
    • We add 8 to our total cost and mark [3,10] as visited.

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 in O(n^2) time because it iterates through all pairs of points.
  • After initializing the graph, there is another loop that runs exactly n times where n 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 of O(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 the n 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 of n x n, which gives a space complexity of O(n^2).
  • The dist list and the vis list each have a size of n, contributing O(n) space each.
  • The other variables (n, i, ans, and the loop index variables) are of constant size and do not depend on n.

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings