Maximum Total Importance of Roads - Leetcode 2285 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum total importance of Roads the idea is we're given a graph like this one it's going to have n nodes it's also going to have some undirected edges that do not have any weights associated with them so all edges are pretty much symmetrical the idea is that we want to number these nodes from one to n in this case we're given five nodes so n equals 5 but we want to give them a number in and we have to use every number from 1 to 5 and we want to do it such that we maximize a certain sum now we're going to calculate that after creating the numbering and basically for every single edge The Edge is going to have a value the value for that edge is basically going to be however many uh edges the node on one side has you can see that this node has two edges and how many edges does this node have well it has three edges so therefore this Edge gets a value of six now we could do that for every single edge I'll just quickly do that this one has one and one or actually this side is three so 3 + 1 that's going to be four here this one is going to be 2 + 3 this one is going to be 2+ 3 as well and then this one is going to also be 2 + 3 and then this one is going to be 3 + 3 so that's six and then every single edge is going to have a value associated with it and the value for each Edge is going to be simple just take the number we assigned to each node that this Edge is attached to each Edge is of course only going to be attached to exactly two nodes we assume there isn't like a self Loop or anything like that but so this one of course is going to be six this one over here just take 5 + 1 and then we get a six and you could do that for obviously every single edge it's not too difficult to do so for this one you do seven this one you get seven as well this one you get eight so after that you take all these numbers add them together and I'm pretty sure we will get 43 assuming that I calcul these correctly so we're trying to maximize this number now with an example like this one it might not be obvious what the solution is but the solution is actually pretty simple so let's look at a slightly different example a smaller one suppose we had a graph like this one so we need to assign a number to each of these and let's just say for Simplicity we do 0 1 2 now we didn't have to do it this way but let's see what the result is now this Edge is going to be 0 + 1 it's just going to be one I'll make it green this one is going to be 1 + 2 so this one is going to be three so the total is going to be four in that case now if I had done it slightly differently if I had actually made this one two and this one one then here for a sum we would have gotten two and here for a sum we would have gotten three and then the result would have been five that's greater so why was the result larger in this one well look at the problem like look at what we're doing how is an edge getting getting values because obviously we're trying to maximize the sum of all edges so how can we make every Edge have as big a value as possible well ideally we want to be greedy don't we like we want to assign this node a value of two rather than zero rather than one we want to give this node a value of two because this node is connected to multiple other nodes therefore it has multiple edges and therefore if we give this a that two is going to be passed down to these two edges that's not going to be the case if we were to give it a one cuz then we'd get a smaller value to these two edges and obviously this one is only going to go here this zero is only going to go here so that's why we want to be greedy and we can do that basically by giving the nodes that have the most edges the largest values so in other words we can map each node to its Edge count so if we did that for this graph over here we get something like this pretty simple and then we would want to go through them in sorted order but we want to go through them based on the edge count like that's what we want to sort by so if you were to take this and sort it based on edge count you'd obviously get zero and two first and then one CU it has a larger Edge count so something like this maybe 0 2 1 but that actually doesn't matter too much because we don't literally have to assign a label to every single node or at least we don't need to know which node is assigned which label because remember what we're trying to do is maximize that sum of like the edges so when we're going through these here these are the nodes themselves but underneath that I'm going to put the edge count it's going to be one one and two so if we were to go through these in sorted order we want to say that this one is going to get a label of zero and then this one is going to get a label of one and then this one is going to get a label of two so that's pretty much what we've drawn up here but if we want to know how much that's going to contribute to the total think of it this way like for here node zero we're giving it a label of zero so basically to the one Edge that belongs to this node we know it has one Edge because of down here this zero is going to be contributed to that one Edge now obviously zero doesn't do anything but if we go to the next one it's going to get more interesting so two we're going to give it a label of one and that one is going to be contributed to the one Edge that belongs to two so the result so far is zero like we're trying to maximize this total so far it's zero but now we've incremented it to one because this one is going to go there lastly we're at the last element this node over here we're going to give it a label of two because that two is going to contribute to this Edge and this Edge we know that because this node has two edges and we can obviously see that here so in other words the equation that we're doing is whatever label this node got multiplied by how many edges that node has so this is going to be a 2 * two that's four so add four to the result and we get five so that's the idea behind this solution to analyze the time complexity we're not doing any sort of traversal on the graph but what we are doing is going through all the edges going through all the nodes and obviously sorting is going to be the bottleneck in this case so sorting let's say there's n nodes is going to be n log n space complexity is going to be bounded by this that's let's say it's going to be Big O of N I think we could be a bit more precise when it comes to this because this is obviously the time complexity of sorting n log n but let's add a plus e here because the number of edges could technically be larger than n log n in the worst case the number of edges without duplicates could be N squared so technically the time complexity to be more precise is n log n + n^ 2 but that's only in the worst case and obviously this is dependent on the number of edges so I think it's more accurate to say plus e if the number of edges is relatively small it won't matter and one last Aster I want to mention with this solution is that it's technically possible that some nodes might actually not be connected like we might have a node here that does not actually connect to the graph so in other words over here it's going to have zero edges so just to deal with this I'm actually going to use an array here rather than a hashmap just because we don't want to skip the nodes that have zero edges like we would still want to assign this a label and probably the smallest label because it doesn't actually have any edges so we' want to start here and then give this a zero and then continue from there it's just a little bit easier to do with an array because with a hashmap the key three would not even exist here so with an array we'll have every single key so to code this up there's two main phases one is just getting the count of each node like the edge count how many edges does each node have that's not too difficult we'll just do something like this N1 N2 in roads and then basically for each of these nodes N1 let's increment it by one and let's do the same thing for the second one then we're going to do the second phase of the algorithm where first of all we're going to make sure that these are sorted so let's sort Edge count and they'll obviously be sorted based on the count like the number of edges node has CU we don't care about the original node at this point so we're just going through these in sorted order the edge count is what we care about and so for count in sorted for each of these we want to add to the result not just the count but we actually want to multiply the count by whatever label that we're giving it so I'm going to call that label initially it's going to be set to one and this makes me realize that I kind of had a mistake in the drawing explanation when we're starting the labeling we're going to go from one up until n so the nodes in this problem are numbered from 0 to n minus one I think that's what was confusing to me I'm sorry about that so when we're actually doing the labeling we want to start this label at one rather than zero so that's the one little thing that you'll have to keep in mind so here we're going to take the count and multiply it by the label just like we did earlier so label multiplied by count so that much is consistent with the drawing explanation the only thing is that we're starting at one not zero now we should probably the result before we start to use it so let me go ahead and do that and let's go ahead and return the result as well now there's just one last thing our label we want to increment it by one each time since we're going through these in sorted order we can't really do that in the for Loop so down here I'm just going to increment label by one so not a lot of code here that's usually the case with greedy Solutions as you can see on the left it works and it's pretty efficient if you found this helpful check out NE code. thanks for watching and I'll see you soon