Minimum Cost Walk in Weighted Graph - Leetcode 3108 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today let's solve the problem minimum cost walk in a weighted graph and wow, this is a five paragraph essay if I've ever seen one in a lead code problem, but don't let it fool you and don't let the difficulty fool you either. I'm going to actually make pretty quick work of this problem. When I say quick work, I mean like figuring out what the solution is and like what the trick is and all that kind of stuff. Coding it up is going to be another story. It's going to be kind of um a pain, but there's several different ways to code this up. I'll probably just code up one of the ways. There is like a DFS solution. There is a BFS solution. I think there's also a union find solution. The union find one is the one I'll be focusing on, but I don't think it really matters. They're roughly equivalent. I mean, I think technically with the real runtime and I guess when it comes to big O, union find is technically more efficient, but it doesn't make as much of a difference as you think. Like for example, just to kind of tell you we're given a graph here. We're given n nodes. We're given e edges and we're given some queries as well. The union find solution is going to be the size of the edges only. We actually don't care about the nodes. So that's where the efficiency improvement comes from union find that the big O complexity is going to be e, the number of edges, plus the number of queries where DFS and BFS I think are going to be different in that the big O complexity is going to be v, the number of vertices, the number of nodes, plus e plus q. So I mean, I really don't think in a real coding interview it would make a difference if you came up with DFS. I think that probably be fine. But anyways, I'll focus on union find. So idea here is that we are given a graph. It is undirected. It is a weighted graph. They don't mention it specifically in the long ass problem description, but down in like the constraints they mention that the edges are not going to be negative. So that's good to know. And what we want to do basically is answer each of these queries. The first query is 0 3. That means we want to find sort of the shortest path. When I say shortest path, it's not literally the shortest path, but we want to find the minimum cost. So that's probably the better way to say it. The minimum cost it's going to take for us to go from 0 all the way to the other node 3. If it's possible, if it's not possible, then we just say -1. And we can clearly see sometimes it's not going to be possible because in this graph we are going to have multiple components. So they make that pretty uh clear from the first example thankfully. So now in terms of actually getting the cost, let's use some of the terminology that they say. They say we're actually looking for a walk, not like a path from 0 to 3. Part of the reason for that is because we're actually allowed to uh revisit the same edge or vertex more than once. So that's usually not the case. So for example, from 0 to 3, yes, we could take straight path, but we could also go down and then come back up and then go to the right and we could also go back to the left and then come back and then we could, you know, do all sorts of things. Among all of those, we want to figure out the one that has the minimum cost, but the cost is not going to be calculated by taking the sum of these because then I think it would be pretty clear that we would never want to revisit the same node or vertex cuz we know there's not going to be negative weights. So now it gets kind of difficult to think about. This is where I got kind of stuck. Well, I guess first let me tell you how we calculate the cost. We're going to take the bitwise and of the edges. So if we took like this path from 0 to 3, we'd take the bitwise and of 7 and 7. Well, generally when you take a number and bitwise and it with another number, it doesn't change. So with 7 and 7, we can expect that the result would be 7. So at this point it seems like pretty simple. Okay, well instead of summing the edges, we're just going to bitwise and them. And then this is the part where I thought, okay, well maybe Dijkstra's algorithm can help us here. Maybe it's just a modified Dijkstra's where instead of summing these we do the bitwise and. But then I thought about it for a second and I thought, well, what is bitwise and actually doing? Because when we sum, we only expect the total cost to get bigger. But with bitwise and, isn't it possible that sometimes our cost could get smaller? And if that's the case, Dijkstra's will not work. That's not what Dijkstra's is for. So now it gets kind of complicated. And this is where I got kind of stuck. Instead of just like staring here and just being frozen and paralyzed, I took a second to think about it a little bit deeper. Maybe go through an example, maybe think about it. If I have a number, let's get into like bitwise anding stuff. Hopefully you guys are at least a little bit familiar with this. I mean, this is a hard problem. So it's hard to kind of learn like 20 things at once with a single problem. So I'm going to assume that you know what this is. If we take some other number 001100 and we were to bitwise and it, we take the bits and if they're both one, then we put a one, otherwise we put a zero. So 0 0 1 0 0 0. Well, I don't know about you, but after I just went through like a single example, it became pretty clear to me what the solution was and what the trick was. When you bitwise and numbers together, is it ever possible that the result would be bigger than both of the uh items that you used to bitwise and? No, that's impossible. In the best possible case, you take the same number x and x and then it'll become x. But if there's ever a part where there's a bit differing, well, then you're just going to get a zero in the output. So I took this away and I took that away and so I ended up with a smaller number. So okay, that seems kind of interesting. I mean, how is that going to help us solve the problem? Well, that's the thing. Remember they told us we could revisit the same guy multiple times. They told us we're trying to minimize the cost and now we determined that bitwise anding is never going to increase the cost. So I don't know about you, but if I'm going from 0 to 3, I'm going to visit every single guy in the graph. Well, what if I visit the same guy twice? I mean, that's going to mess up our calculation. No, it's not. Like I said, the same number anded with the same number is not going to change. And the way and properties work, if I give you a bunch of numbers x anded with y anded with z and I change the order of these, it doesn't matter. So for us to get the minimum cost of one node to another node in any given component, this is one component, all I need to do is just take every edge bitwise and it. I'm going to take seven bitwise and it with seven bitwise and it with one. I believe seven is something like this in binary and then one is just this. Or no, I think a seven is actually this, 111, and then one is this and then we get a one in the output and then that answers a single query. Now for all the other queries, we could do it the exact same way. So what this problem boils down to is doing a bunch of pre processing. And what that pre processing is is get every single component in the graph, like separate every component. There's many different ways to do this. You could use union find. It's pretty natural to do it that way. You could do DFS. You could do BFS. I'm going to be doing it with union find. So you can pick your poison. Next, after we do that, for every component, get the cost of it. Now, how do you get the cost? Pretty easy. Just get every edge belonging to a component and then bitwise and them together. Now there's a slight like edge case where like let's say here I have two different components. And so initially I could say, okay, well, the bitwise and so far of this component is zero. So far of this component, it's zero. And now I want to start updating the bitwise and. So I do zero anded with seven anded with one. Anytime you and zero with anything, zero anded with x is always going to be zero because zero doesn't have any bit set. So that's kind of an edge case where we can just handle pretty easily in the code. I'll show you how to do that. Uh but that's the whole idea. So after we do this pre processing, and it's going to take uh some work. It's going to take us to go through all of the edges. So the time complexity of the pre processing is just going to be e. And then to answer each query, we have to iterate over every query. That's going to be at least plus q, but to answer each query, it's going to be constant time. Because the pre processing is going to for this component, we're going to have the cost of that component. So anytime we want like one node to another within that component, well, just return the cost. It's that simple. From here to here, the shortest path should be the same as the shortest path from here to here. And when I say shortest path, of course, I mean cost. And if it's not possible, like if we're trying to go from here to over here, well, then we can just say the cost is -1 cuz that's not possible. So this time complexity should be pretty efficient. Now, I think this video will probably end up being long enough cuz the coding portion is going to be pretty long. So, I'm not going to cover the drawing explanation of Union-Find. Like I said, you could do DFS or BFS if you prefer. This is a very hard problem, so I think it is worth getting really good at the basics before you try to tackle a problem like this one. I think today's problem specifically, some of these graph algorithms, or I guess uh the um Union-Find lesson would probably be pretty helpful. I think if you're just new to Union-Find, it has a lot of uh deep explanations, and then you can like go ahead and implement Union-Find uh by yourself in whatever language you want to. Okay, so now let's code it up, and I'm going to reset this, but I wanted to show you what my thought process was when I was going through this. So, I kind of just took some notes about the problem. So, we're thinking about the cost of a walk. That seemed important. We want to get the bitwise and of the weights. So, this problem is probably related to that. Multiple components, non-negative weights. And then I thought at first, why would we ever want to revisit the same node multiple times anyways? That's not really how the shortest path algorithm works. Isn't it possible for us to just do an augmented Dijkstra's? And then I realized, no, because with and, numbers could get smaller. And then, of course, I realized that that's the point. With and, numbers only get smaller, or they could stay the same. And then that's when I basically figured out the solution. So, pretty much what I kind of talked about in the previous part. But, first, I'm going to just declare my Union-Find class over here. That's where the bulk of this code is actually going to go. I'll just fill in a little bit for now. We'll have our constructor. It'll take a parameter n, telling us how many nodes we're dealing with. We'll track the parent of each node. Initially, each node can be its own parent. So, in Python, we can actually do this. The range of n. This will give us zero through n minus one. We'll convert it into a list like that. Then, we can also keep track of the sizes of each uh node. So, initially, we can say that'll be one for each. And then we're going to have a couple functions, find a root of a node, and the union function, where we take two nodes and then combine the components together. So, I'll fill these in afterwards, but in a real interview, if I were you, I wouldn't fill this in first. I would just assume that you have a working way to do Union-Find, and then focus on the rest of the problem, and then you can come back to this. Now, if you don't know how to solve the rest of the problem, then maybe yeah, you should fill in this part. But, now down here, what I'm going to do is create an instance of that Union-Find class, passing in n. Then, I'm going to get all the components. We can do that pretty easily. Just go through every edge. Each edge is weighted. We're going to unpack the first node, the second node, and the weight. We won't really use the weight. We just want to union uh uf.union these two components together. And after that's done, we assume that Union-Find will be able to track the components. So, for each uh component, we should be able to get the root parent. So, next, after building, we're going to get cost of each component. And this isn't super difficult to do. It does take a little bit of thought, but what I'm going to do here is create a hash map. So, I'm going to map each component, the root of the component, to the cost. So, we can do that like this, just iterating over the edges once again, and then we can take either of these two nodes. We know for sure these two nodes are connected. I mean, they're literally connected through this edge. So, we can just pick either of them to get the root parent. So, uf.find, I'll pass in u, and I'll call this my root. Now, if I say, if root is not in the component cost, then I'm just going to set the component cost equal to w. Otherwise, then I'm going to do the bitwise anding. So, let me just copy and paste that, and then do the and over here. And the reason for this is because one, we don't want to get the key out of bounds error. But, even more importantly, if the component cost was zero, and we try to zero and with another number, it's going to stay as zero forever. That's not really what we want. Okay, now after that, the last phase is just the actual queries. So, that's pretty easy. Well, initially, I'll have my result. That's what I want to return. I'm going to have my queries. It's going to be a source-destination pair in each. I want to get the root of each one. So, I'll say root one, root two, and then I can do Union-Find. find source, and find the destination. Because it's not guaranteed that these two nodes are a part of the same component. That's the whole point of the query. So, now we're going to say, if the roots are not equal, if r1 does not equal r2, well, then they're not connected. So, for this query, the answer is going to be -1. Otherwise, uh we can just take either of these two roots, because they're obviously the same if the if statement didn't execute. We can then go into component cost, pass in either of those. So, now we have the cost of that component, and we know that this is the answer to the query. So, we say result.append. Now, we're almost done. You can see that this code wasn't really too bad once you kind of know the trick. But, doing this Union-Find stuff going to take a couple more minutes. So, here we want to find the root. I'm going to do that recursively. I'm going to say, if my current x is not equal to the parent of x, that means that we have a different parent. So, let me find the root parent recursively. I'm going to say, self.find the parent of x. So, uh I'm going to pass in the parent of x. So, instead of calling this on x, we're calling it on the parent of x. So, we're going up the tree. And then, after that, this should give us the uh root parent, and then down here, we can return that root parent. And this is because we initialized the parent array, where each node was the parent of itself. Again, if you're not familiar with Union-Find, I would highly recommend checking out some resources to learn this stuff in depth. NeetCode.io has uh several videos on that. In this function, we just want to connect x and y. We can just find the root parent of each, and if they are not equal, well, then we can union them together, and we're going to be doing a union by size. This makes this very efficient. Practically constant time. Not literally constant time. There's something called the Ackermann function that you can learn about on NeetCode. But, practically constant time. So, here we're going to check which one of these is smaller. So, if the self.size is uh smaller than the other one, then we're going to do this. The parent of x is going to become y. We take the smaller one and make it the child. And then, to the size of y, we add the size of x. And in the else case, we basically just do the opposite. So, I'm going to copy and paste this, and just flip it around. So, y will have the other parent, and the size will be added to the other guy. And if we wanted to in this function, we could return like a true or false, depending on whether we actually performed a union, or maybe we didn't perform a union, we could return false. Doesn't really matter in this problem though, so I will not put those. But, yeah. So, this is quite a hefty solution. You can see the Union-Find code is about 20 lines, and then the rest of this is also about 20-25 lines of code. And here on the left, you can see that it does indeed work, and it is pretty efficient. If you found this helpful, check out NeetCode.io for a lot more. Thanks for watching, and I'll see you soon.