Prim's Algorithm - Minimum Spanning Tree - Min Cost to Connect all Points - Leetcode 1584 - Python

0:00 - Read the problem
3:44 - Drawing Explanation
16:32 - Coding Explanation

leetcode 1584

#prims #algorithm #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[anotheredits]

you have no idea how helpful your videos have been to me
I went through 2 articles and 2 youtube videos before I realized you have a video on Prim's Algorithm (yes I'm kind of oblivious)
and then it became pretty clear to me.
Thank you man, cheers

[ameynaik]

Excellent video, main take away is, it is just like BFS + priority queue (instead of queue in BFS) ; also you will be adding duplicates hence complexity to pop from the min-heap is n^2*log(n)

[Grawlix]

As other commenters have mentioned, we don't need to generate all edges ahead of time. It's more efficient to track 'remaining' points and only generate edges for points that still need to be visited. For all remaining unvisited nodes, we can calculate the edge cost and push it to the minheap directly. Here's my code (don't get hung up on the lambda, it's just an 'in-inline' function):

def minCostConnectPoints(self, points: List[List[int]]) -> int:
manhattan = lambda p1, p2: abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
pq = [(0, tuple(points[0]))]
mincost = 0
toVisit = set([tuple(x) for x in points])

while pq:
curCost, curNode = heapq.heappop(pq)
if curNode not in toVisit:
continue
toVisit.remove(curNode)
mincost += curCost
if len(toVisit) == 0:
break
for n in toVisit:
heapq.heappush(pq, (manhattan(curNode, n), n))

return mincost

[garvitbhatia]

I am so used to your coding style, I coded this question up by myself in c++ and it is the same, literally the same how you did it. Great list.

[tusov]

The tutorial is totally smooth and helpful.
You are definitely one of the my best ds and algo online mentor during hunting job (the other is genius Erik Demaine ...)
Again, appreciate your knowledge sharing and thank you so much!!!

[trantung]

Precalculating all the edge length is quite time consuming. The distance from one vertex to every remainings should be calculated in the while loop below since the length of vertices will be reduced after each step.

[brianevans]

Great walkthrough - LC Explore does a good job of explaining algorithms, but doesn't do anything for implementing. Walking through with code was very helpful.

[hongliangfei]

You are the go-to channel once I want to learn anything

[crit]

This channel is the best when it comes to LC solutions. Could you please make a video on "Subarray sum equals K" and "Maximum size subarray sum equals k". These problems are based on the concept of hashmap in 2 sum, yet when it comes to implementation, they are not that trivial.

[VarunMittal-viralmutant]

Came across this alternate solution to implement the same Prim's algo
This one is simpler :)

d = dict()

# Take first point and make it's cost as 0 all others infinity
for i, (x, y) in enumerate(points):
if i:
d[(x, y)] = float("inf")
else:
d[(x, y)] = 0

ans = 0
# While there are still more points left
while d:
# Get the point with minimum cost
x, y = min(d, key=d.get)
# Add to current cost and remove the point from dict of points
ans += d.pop((x, y))

# Relax/re-calculate cost of all the points from this point
for x1, y1 in d:
d[(x1, y1)] = min(d[(x1, y1)], abs(x - x1) + abs(y - y1))
return ans

[chinesemimi]

Since we are finding the MST in a dense graph (a graph with many edges) - the complete graph, Prim’s algo is more efficient in basically every case.

[MinhNguyen-lzpg]

nice solution and explanation! we actually need either of the checking condition for point in visited. Having both does not affect the overal TC.

[paddyd]

You can think about the complexity as when you have n points optimal connected, to include another point, you need to find the best way to connect the point from every single already connected point. So each inclusion of another point is nlogn.

[woostanley]

This is such a great and well-explained video.

[ashutoshlohogaonkar]

Thank you for a such a detailed video explaining Prim's algorithm and building the solution..

[sammyj]

What a beautiful explanation! I am going to implement this in C++. Thanks for the video!! Learning a lot from your channel and I am also aiming to become a Noogler soon :)

[HenockTesfaye]

You saved me! Thank you. Forever grateful

[reaiswaryaa]

You are an awesome teacher, thank you for your videos ❤️

[benzz]

honestly if you taught a course, i would buy it. i dont normally consider them but you teach different :)

[EranM]

You can calculate distances on the fly,
You don't have to get the full ADJ list, because PRIM is greedy. Every time you add a node, you don't need anything related to it for the next iterations...
Just address all nodes as unconnected components and start connecting them using the minimum distance from the frontier.