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.

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

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.