Min Cost to Connect All Points - Codey

Description Submissions Solution

Description Submissions Solution

Loading...

Log in to run or submit

points =

Codey

Practise coding problems, test your solutions and track your progress.

Explore

Problems
About
Contact

Legal

Privacy Policy
Terms of Use

© 2026 Codey. Personal learning project.

Solution

Updated: 2026-02-23

Idea

Minimum cost to connect all points is an MST with Manhattan edge weights.

Approach

Prim’s algorithm without building all edges explicitly:

Maintain best known distance to the growing MST for each point.
Use a min-heap of (cost, pointIndex).
When adding a point, relax distances to all remaining points using Manhattan distance.

Why it works

Prim’s algorithm greedily grows an MST by always adding the cheapest edge to a new vertex.

Code

Loading...

Complexity

Time: O(n^2 log n)

Space: O(n)

Solution

Updated: 2026-02-23

Idea

Minimum cost to connect all points is an MST with Manhattan edge weights.

Approach

Prim’s algorithm without building all edges explicitly:

Maintain best known distance to the growing MST for each point.
Use a min-heap of (cost, pointIndex).
When adding a point, relax distances to all remaining points using Manhattan distance.

Why it works

Prim’s algorithm greedily grows an MST by always adding the cheapest edge to a new vertex.

Code

Loading...

Complexity

Time: O(n^2 log n)

Space: O(n)