Skip to main content
Talentd

Min Cost to Connect All Points - Solution & Explanation

MediumArrayUnion FindGraphMinimum Spanning Tree24 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

 

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

Approach Overview

Problem Overview: You are given n points on a 2D plane. The cost to connect two points equals their Manhattan distance |x1-x2| + |y1-y2|. The goal is to connect every point so that all points are reachable from each other while minimizing the total connection cost. This is a classic Minimum Spanning Tree (MST) problem on a complete graph where each pair of points forms an edge weighted by Manhattan distance.

Approach 1: Kruskal's Algorithm with Union-Find (Time: O(n^2 log n), Space: O(n^2))

Model the problem as a graph with n vertices. Since every pair of points can connect, generate all n(n-1)/2 edges and compute their Manhattan distances. Sort these edges by cost. Then iterate through the sorted list and use a Union-Find (Disjoint Set Union) structure to check whether two points already belong to the same component. If they do not, union them and add the edge cost to the total. Continue until n-1 edges are selected. This greedy strategy guarantees a valid MST because edges are processed from smallest weight to largest. This approach works well when you are comfortable managing edge lists and union operations using Union Find.

Approach 2: Prim's Algorithm (Time: O(n^2), Space: O(n))

Prim's algorithm builds the MST incrementally. Start from any point and mark it as visited. For every unvisited point, maintain the minimum cost required to connect it to the current MST. At each step, pick the unvisited point with the smallest connection cost, add it to the MST, and update distances for the remaining points. Because the graph is dense (every pair of points has an edge), computing distances on the fly avoids storing all edges. This leads to O(n^2) time and O(n) extra space. The approach relies heavily on greedy expansion and is often easier to implement for dense graph problems involving minimum spanning tree construction.

Recommended for interviews: Prim's algorithm is usually the expected solution. The graph is fully connected, so generating all edges for Kruskal introduces unnecessary overhead. Demonstrating Kruskal first shows you recognize the MST pattern, but implementing Prim with a distance array shows deeper understanding of how MST algorithms behave on dense graphs.

Approach 1: Approach 1: Kruskal's Algorithm with Union-Find

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:

  • Calculate the Manhattan distance between all pairs of points to create the edges of the graph.
  • Sort all edges by their weight (distance).
  • Initialize a Union-Find (Disjoint Set Union) structure to track connected components.
  • Iterate through the sorted edge list, adding an edge to the MST if it connects two previously unconnected components.

This approach efficiently computes the minimum cost of connecting all points.

This implementation first constructs all the edges with their distances, using a nested loop to calculate the Manhattan distance between each pair of points. Then, it sorts the edges by distance. The Union-Find structure is initialized and used to progressively add edges to the Minimum Spanning Tree as long as they connect previously disconnected components. The function returns the total cost of the spanning tree.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Prim's Algorithm

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:

  • Initialize an array to track minimum costs from each node.
  • Use a priority queue to select the next edge with the smallest cost.
  • Iterate over nodes, updating the priority queue with potential edges to unvisited nodes.

This approach offers a clear alternative to Kruskal's, particularly well-suited to densely connected systems.

This C version uses an array to track visited nodes and another to store the minimum weight edge for each node, initialized to infinity. The central loop iterates over all nodes, expanding the MST by connecting the node with the minimum edge weight. It updates the minimum weights for reachable unvisited nodes at each step.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Kruskal's Algorithm with Union-Find

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.

Approach 2: Prim's Algorithm

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Kruskal's Algorithm with Union-FindO(n^2 log n)O(n^2)When you want a straightforward MST approach using sorted edges and Disjoint Set Union.
Prim's Algorithm (Array-based)O(n^2)O(n)Best for dense graphs like this one where every pair of nodes can connect.

Video Solution

Prim's Algorithm - Minimum Spanning Tree - Min Cost to Connect all Points - Leetcode 1584 - Python • NeetCode • 147,569 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Min Cost to Connect All Points easy or hard?
LeetCode classifies the problem as Medium difficulty. The main challenge is recognizing that the points form a complete graph and that the task reduces to building a Minimum Spanning Tree using algorithms such as Prim or Kruskal.
Min Cost to Connect All Points Python/Java solution
Most implementations use either Kruskal with Union-Find or Prim's algorithm. Python solutions often implement Prim with a distance array for O(n^2) complexity, while Java and C++ versions may use either Prim or Kruskal depending on preference.
How to solve Min Cost to Connect All Points in O(n^2)?
Use Prim's algorithm with a distance array. Start with any point, track the minimum cost needed to connect each remaining point, and repeatedly add the closest unvisited point to the MST. Update distances using Manhattan distance calculations. This avoids building all edges and achieves O(n^2) time.
What is the best approach for Min Cost to Connect All Points?
Prim's algorithm is typically the best approach. The graph formed by all points is dense because every pair can connect, so generating all edges for Kruskal is unnecessary. Prim's algorithm computes distances on demand and runs in O(n^2) time with O(n) space, making it efficient and simpler to implement.
Is Min Cost to Connect All Points asked at Google/Amazon/Meta?
Min Cost to Connect All Points appears frequently in interviews at companies that test graph fundamentals such as Amazon, Google, Meta, and Microsoft. It evaluates understanding of Minimum Spanning Tree algorithms like Kruskal and Prim along with union-find data structures.
What data structure is used in Min Cost to Connect All Points?
Common structures include Union-Find (Disjoint Set Union) for Kruskal's algorithm and arrays or priority queues for Prim's algorithm. These help track connected components or the minimum edge needed to expand the current Minimum Spanning Tree.
What is the time complexity of Min Cost to Connect All Points?
The optimal implementation using Prim's algorithm runs in O(n^2) time and O(n) space. A Kruskal-based solution requires generating all edges between points, which leads to O(n^2 log n) time due to sorting the edge list.

Ready to solve this problem?

Practice Min Cost to Connect All Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Lines to Cover Points