loading

Min Cost to Connect All Points — Step-by-Step Visualization

mediumLeetCode #1584ArrayGraphMinimum Spanning TreePrim's AlgorithmKruskal's Algorithm

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|`. Return the minimum cost to make all points connected.

Algorithm Pattern

Minimum Spanning Tree (MST)

Key Idea

This problem is a classic Minimum Spanning Tree problem where the nodes are points and the edges are the Manhattan distances between every pair of points. Using Prim's Algorithm: we start from an arbitrary point, maintain a min-heap of the smallest distances to points not yet in the MST, and greedily add the closest point until all are connected.

Step-by-Step Approach

  1. Initialize `adj` list where each point connects to all others with Manhattan distance.
  2. Initialize `minHeap` with `(0, 0)` (cost 0, start at point 0) and `visit` set.
  3. While `len(visit) < n`:
  4. Pop `(cost, i)` from heap. If `i` in `visit`, continue.
  5. Add `cost` to `res`, add `i` to `visit`.
  6. For each neighbor `(cost_ni, ni)` of `i`, if `ni` not in `visit`, push to heap.
  7. Return total `res`.

Common Gotchas

  • Wait, generating all $N^2$ edges up front is fine since $N$ is small (up to 1000, but usually less in visualizers).
  • Manhattan distance is $|x1-x2| + |y1-y2|$.

Related Problems

← All problems