This problem requires finding the minimum cost to connect all points in a 2D plane, where the cost between two points is the Manhattan distance. We can use Prim's algorithm to solve this problem. Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

The core idea is to start with an arbitrary node and iteratively add the cheapest edge that connects a visited node to an unvisited node. This process continues until all nodes are visited, resulting in a minimum spanning tree. The sum of the edge weights in this tree is the minimum cost to connect all points.

Intuition:

Imagine each point as a city, and the Manhattan distance between them as the cost to build a road. We want to build roads connecting all cities such that the total cost is minimized. Prim's algorithm helps us find the optimal set of roads to build. This is like growing a tree from a starting city, always picking the cheapest road to a new, unconnected city.

Prim's algorithm builds the MST (Minimum Spanning Tree) by repeatedly adding the minimum weight edge connecting a vertex in the tree to a vertex not yet in the tree. We use a min-heap to efficiently find the minimum weight edge.

Step-by-step thinking:

Build the adjacency list representing the graph. Each node is a point, and the edges are the Manhattan distances between the points.
Initialize a set `visit` to keep track of visited nodes and a min-heap `minHeap` to store edges with their costs. Start with an arbitrary node (e.g., node 0) and add it to the min-heap with a cost of 0.
While there are unvisited nodes (i.e., `visit.size < N`), extract the minimum cost edge from the min-heap.
If the destination node of the extracted edge has already been visited, skip this edge.
Otherwise, add the cost of the edge to the `result`, mark the destination node as visited, and add all its adjacent edges (connecting it to unvisited nodes) to the min-heap.
Repeat steps 3-5 until all nodes are visited.
Return the accumulated `result`, which represents the minimum cost to connect all points.

Time Complexity: O(N^2 log N), where N is the number of points. Building the adjacency list takes O(N^2) time. The while loop runs at most N times, and each time we extract the minimum from the min-heap (O(log N)) and iterate through the neighbors of a node (O(N) in the worst case), so the total time complexity is O(N^2 log N).
Space Complexity: O(N^2), to store the adjacency list and the min-heap.
Learn Complexity

26. Prim's Algorithm

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases