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

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

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

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)

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

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

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.

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 :)

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

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

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

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

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.

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.

Really grateful for the awesome explanation

Great video! Thank you!

You saved me! Thank you. Forever grateful

very helpful! clear explanation!

would doing the calculations in prims be more optimal, if so how would we do it?

This is such a great and well-explained video.

Awesome video NeetCode you are best 🎉

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

We are pushing a neighbor only when not in visit set, then in that case do we have to check again and continue?

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.

Great Explanation !!!

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.

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.

Ok, can you clarify why did not we just do compare each node with everyone and take the min values and add them up? it will be n^2. is it because we want to prevent a cycle?

You sir, are a legend.

As always, thank you !!

Thanks for the tutorial. I’d feel more comfortable with matrix indexing tho.

At 15:35, from 2nd node to 1st node we are adding edge as it has min cost of 9, but won't it violate the line if nei not in visit(26th line in code) as 1st node is already in visit set?

Thank you for your video, this is very valuable! There is an optimized Prime's method from Leet code solution. The time complexity can be optimized into O(N^2). Could you talk a little about that?

you mentioned that there are some other algorithms for this type of problem, will you be doing videos on those anytime as well?

Isn't line 26 redundant though? Since we are already continuing at line 21 if a node is already seen. I just checked and it works just fine when I comment line 26.

Great video

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

can you cover other algorithms like kruskal, dijkstra etc.

Please, can you also someday add to your course on your website video on Kosaraju's Algorithm

How can you start at an arbitrary node instead of starting at the node with the min edge that connects to it

Great video. Isn't the time complexity O(n2 log n2) instead of O(n2 log n)? Can't the heap size reach higher than n

shouldn't we heapify the list first?

When building the adj list, I thought you want to add every other nodes? but you are adding all nodes j for node i, where j>i. So you did: for i in range(N): for j in range(i+1, N): # build adj list but instead should it be: for i in range(N): for j in range(N): if i == j: continue # build adj list

You are the legend

As of now this solution is getting TLE on LC, because of a huge test case. To avoid it, calculate the Manhattan distance inside the Prims algorithm part. Only maintain neighbours list in the adjacency hashmap.

Hello everyone. Please how can we implement this to an actual question? I have an assignment and went through the video. I understood the first part but have issues implementing it in my assignment. Many thanks

How is it n^2 * log(n) and not instead n^2 * log(n^2)? If the heap can have n^2 elements in it, each heap operation is going to be log(n^2), no?

can you drop a link to c++ code for this ques?

Isn't your solution O(N^2) instead of O(N^2LogN)? I see it as creating the adj list takes O(N^2) then Prim's takes O(NLogN).

How's it different than Djkistra Algo? @neetcode

This looks like an O((E+N) lg N) where E=N^2 so O(N^2 lg N)? isn't there a O(N lg n) solution?

your channel is a goldmine

So nice

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.

Don't you need to heapify minH?

for a dense graph like this, adjacency matrix will be better.

wow Thanks

is this a TSP?

I did the same thing as the code in this video in JavaScript and it took 2 seconds to run on leetcode, changed it to be like Bellman Ford and it lowered down to 152ms. Bellman ford complexity on this should be runtime O(n^2) and memory O(n). I think the Prim's algorithm as implemented in this video is runtime O(n^2 + n*log n + n^2 * log n) (build adj list, pop heap n times, push to heap n*n times) since it's pushing to the heap n^2 times (in nested for loop). It would be cheaper to just recalculate the distance with every point than pushing to the heap for every element on every iteration. I think proper prims algorithm is meant to be different.

Sorry for being a stickler but, I couldn't help but notice from a couple of your videos that you write the incorrect spelling of Dijkstra's Algorithm😅

🐐

Leetcode does not ask, but the algorithm presented does not provide a tree as output, only the cost.

❤❤

JAVA Solution With Custom Min Heap Implementation. intentionally avoided PriorityQueue existing minHeap in Java for learning. record HeapValue(int cost, int node) {} class Solution { public int minCostConnectPoints(int[][] points) { ArrayList heap = new ArrayList(); HashMap map = buildMap(points); HashSet set = new HashSet(); int cost = 0; insert(heap, new HeapValue(0, 0)); while(set.size() < points.length) { HeapValue currentNode = remove(heap); if(set.contains(currentNode.node())) continue; cost += currentNode.cost(); set.add(currentNode.node()); if(!map.containsKey(currentNode.node())) continue; for(HeapValue neighbor : map.get(currentNode.node())) { if(!set.contains(neighbor.node())) { insert(heap, neighbor); } } } return cost; } private HeapValue remove(ArrayList heap) { HeapValue min = heap.get(0); heap.set(0, heap.get(heap.size() - 1)); heap.remove(heap.size() - 1); heapify(heap, 0); return min; } private void insert(ArrayList heap, HeapValue node) { heap.add(node); int length = heap.size() - 1; while((length - 1) / 2 >= 0 && heap.get((length - 1) / 2).cost() > node.cost()) { HeapValue tmp = heap.get((length - 1) / 2); heap.set((length - 1) / 2, node); heap.set(length, tmp); length = (length - 1) / 2; } } private void heapify(ArrayList heap, int node) { if(heap.size() == 0) return; int smaller = node; int leftChild = 2 * node + 1; int rightChild = 2 * node + 2; if(leftChild < heap.size() && heap.get(leftChild).cost() < heap.get(smaller).cost()) { smaller = leftChild; } if(rightChild < heap.size() && heap.get(rightChild).cost() < heap.get(smaller).cost()) { smaller = rightChild; } if(smaller != node) { HeapValue tmp = heap.get(node); heap.set(node, heap.get(smaller)); heap.set(smaller, tmp); heapify(heap, smaller); } } private HashMap buildMap(int[][] points) { HashMap map = new HashMap(); for(int i = 0; i < points.length; i++) { int[] currentPoint = points[i]; for(int j = i + 1; j < points.length; j++) { int[] nextPoint = points[j]; int distance = Math.abs(currentPoint[0] - nextPoint[0]) + Math.abs(currentPoint[1] - nextPoint[1]); if(map.containsKey(i)) { map.get(i).add(new HeapValue(distance, j)); } else { ArrayList list = new ArrayList(); list.add(new HeapValue(distance, j)); map.put(i, list); } if(map.containsKey(j)) { map.get(j).add(new HeapValue(distance, i)); } else { ArrayList list = new ArrayList(); list.add(new HeapValue(distance, i)); map.put(j, list); } } } return map; } }

popping min is O(1) operaton not a logn

The solution is great, however one of the test case fails `points = [[0,0],[1,1],[1,0],[-1,1]]` calculating the edges uses (i+1) in inner loop, which is causing the issue

it's pronounced dike-struh lmao 💀

Sorry buddy you use a lot of words but still not clear. A lot of the Indian youtubers explain much more clearly.