<p>You are given an array <code>points</code> representing integer coordinates of some points on a 2D-plane, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>.</p>

<p>The cost of connecting two points <code>[x<sub>i</sub>, y<sub>i</sub>]</code> and <code>[x<sub>j</sub>, y<sub>j</sub>]</code> is the <strong>manhattan distance</strong> between them: <code>|x<sub>i</sub> - x<sub>j</sub>| + |y<sub>i</sub> - y<sub>j</sub>|</code>, where <code>|val|</code> denotes the absolute value of <code>val</code>.</p>

<p>Return <em>the minimum cost to make all points connected.</em> All points are connected if there is <strong>exactly one</strong> simple path between any two points.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/d.png" style="width: 214px; height: 268px;" />
<pre>
<strong>Input:</strong> points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
<strong>Output:</strong> 20
<strong>Explanation:</strong> 
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/26/c.png" style="width: 214px; height: 268px;" />
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> points = [[3,12],[-2,5],[-4,1]]
<strong>Output:</strong> 18
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 1000</code></li>
	<li><code>-10<sup>6</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li>All pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are distinct.</li>
</ul>

from collections import defaultdict
from heapq import heapify, heappop, heappush

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        edges = defaultdict(dict)
        for x1, y1 in points:
            for x2, y2 in points:
                if (x2, y2) not in edges[(x1, y1)] and (x1, y1) != (x2, y2):
                    distance = abs(x1-x2) + abs(y1-y2)
                    edges[(x1, y1)][(x2, y2)] = distance
                    edges[(x2, y2)][(x1, y1)] = distance
        
        heap = []
        heapify(heap)
        heappush(heap, (0, tuple(points[0]), tuple(points[0])))
        
        visited = set()
        cost = 0
    
        while(len(visited) != len(points)):
            distance, from_point, to_point = heappop(heap)
            if to_point in visited:
                continue
            else:
                visited.add(to_point)
                cost += distance
                for edge_point in edges[to_point]:
                    heappush(heap, (edges[to_point][edge_point], tuple(to_point), tuple(edge_point)))
        
        return cost
    
"""
TC is O(n^2logn) SC is O(n^2)
Prim's Algo has complexity ElogV where E is number of edges and V is number of vertices.
If number of vertices is n, then number of edges is proportional to n^2. So TC is O(n^2logn)
This makes sense since maximum size of minheap is number of edges = n^2. Each Insert and Delete to minheap is nlogn. So overall TC is O(n^2logn).
SC is max size of minheap which equals n^2

This is Prim's algorithm to find minimum spanning Tree
Construct a min-heap of structure (distance, from_edge, to_edge)
visited is a set of visted nodes.
while(we have not yet visited all nodes):
    distance, from_point, visit_point = heappop(heap)
    if to_point node has been visted:
        continue
    else:
        Add to_point to visited.
        Increment cost by distance
        For every edge_point from to_point:
            Push (distance, to_point, edge_point) to minheap
            
return cost

"""
                
203874