Min Cost to Connect All Points

Problem

https://leetcode.com/problems/min-cost-to-connect-all-points/

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x:sub:`i`, y:sub:`i`].

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
-10:sup:`6`<= x:sub:`i`, y:sub:`i`<= 10:sup:`6`
All pairs (x:sub:`i`, y:sub:`i`) are distinct.

Pattern

Array, Union-Find, Graph Theory, Minimum Spanning Tree

Approaches

Prim’s Algorithm

Explanation

We can use Prim’s algorithm to find the minimum spanning tree of the graph formed by the points. We start with an arbitrary point p = points[0] and initialize a min-heap of edges from p to all other points. We then repeatedly extract the minimum edge from the heap, add it to the MST, and add all edges from the newly added point to the heap. If the minimum edge connects two points that are already in the MST, we discard it and proceed with the next minimum edge. We continue this process until we have added all points to the MST.

Code

import heapq


def dist(p, q):
    """Returns the L1 distance between 2D points ``p`` and ``q``."""
    return abs(p[0] - q[0]) + abs(p[1] - q[1])


def minCostConnectPoints(points: list[list[int]]) -> int:
    """Returns the minimum cost to connect all points where the cost to connect
    any two points is their L1 distance.
    """
    points = [(x, y) for [x, y] in points]

    visited = set()
    p = points[0]
    visited.add(p)
    edges = [(dist(p, q), p, q) for q in points if p != q]
    heapq.heapify(edges)

    total_cost = 0
    while len(visited) < len(points):
        cost, p, q = heapq.heappop(edges)
        if q in visited:
            continue

        visited.add(q)

        total_cost += cost

        for r in points:
            if r not in visited:
                heapq.heappush(edges, (dist(q, r), q, r))

    return total_cost

Test

>>> from min_cost_to_connect_all_points__prims_algorithm import minCostConnectPoints
>>> minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])
20
>>> minCostConnectPoints([[3,12],[-2,5],[-4,1]])
18

Complexity

Measure	Complexity	Notes
Time	\(O(n^2 \log n)\)	Prim’s algorithm is \(P(E log V)\) where, here, we have \(n^2\) possible “edges” and \(n\) nodes
Auxiliary Space	\(O(n^2)\)	min heap of edges

min_cost_to_connect_all_points__prims_algorithm.dist(p, q): Returns the L1 distance between 2D points p and q.

min_cost_to_connect_all_points__prims_algorithm.minCostConnectPoints(points: list[list[int]]) → int: Returns the minimum cost to connect all points where the cost to connect any two points is their L1 distance.