:orphan:

Min Cost to Connect All Points
==============================

.. highlight:: none

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```\ ``]``.

The cost of connecting two points
``[x``\ :sub:```i```\ ``, y``\ :sub:```i```\ ``]`` and
``[x``\ :sub:```j```\ ``, y``\ :sub:```j```\ ``]`` is the **manhattan
distance** between them:
``|x``\ :sub:```i```\ ``- x``\ :sub:```j```\ ``| + |y``\ :sub:```i```\ ``- y``\ :sub:```j```\ ``|``,
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:**

|image1|

::


   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.

.. |image1| image:: https://assets.leetcode.com/uploads/2020/08/26/d.png

.. highlight:: python

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

Approaches
----------

.. tab-set::

    .. tab-item:: Prim's Algorithm

        **Code**

        .. literalinclude:: ../problems/medium/min-cost-to-connect-all-points/min_cost_to_connect_all_points__prims_algorithm.py
            :language: python
            :lines: 9-

        **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

        .. autofunction:: min_cost_to_connect_all_points__prims_algorithm.dist

        .. autofunction:: min_cost_to_connect_all_points__prims_algorithm.minCostConnectPoints