Robot Collisions - Leetcode 2751 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today I'll solve the problem robot collisions so there's just going to be one solution for this problem so that's the good thing now as for the description here um blah blah blah let's just get straight to the example so the idea is we're given a bunch of robots on a one-dimensional line of some sort so we have the position of each robot it's going to be distinct no two robots are going to start at the same position so that's very important in the context of this problem because what this problem is about is robot collisions as the name implies so if two robots ever land on the same position one of them is guaranteed to be destroyed so that's kind of the gist of the problem now let's get into it each robot has a certain amount of health so you can see that this robot is at position five so even though it's first in the array it's actually all the way over here now at that same index we have a corresponding health notice that the health of this robot is two cool now this part kind of bugs me they give us two input arrays and then for the direction that the robot is moving in it could either be left or right they don't give us an array they give us a string which is fine but I don't know maybe it's OCD or something but that kind of bothered me I don't know in any case in this example it's very simple every robot is moving to the right so there's not going to be any collisions among any of these these five robots now even though this is a simple example it can still teach you a couple things one the speed doesn't matter we're not given the speed of any of the robots so how do we determine if two robots Collide well they're moving in opposite directions right or is it true that like opposite directions is fine cuz if I have one robot moving to the left and have another robot moving to the right they're probably not going to collide right so the only way they're going to Collide is if the robot on the left is moving to the right and the next robot is moving to the left when I said the next robot what does that mean to you the next robot that shows up in the next position or like the next position of the input array no probably the next robot in terms of like chronological order based on like the position of each robot from left to right so probably we might want to sort the input based on the position okay interesting now again this first example is pretty interesting because let's assume we go through each robot in sorted order based on the position we go to this robot first even though it shows up last in the input we see this robot is moving to the right that's fine next robot is moving to the right that's fine next robot is moving to the right that's fine as well it's just going to keep going like that there's no collisions right so now let's consider the opposite case I got a robot moving to the left that's fine another robot moving to the left that's also fine now if I had a robot moving to the right that's also fine by me so one thing I noticed is that if I have a robot like let's say at the beginning of the input and it's going to the left it's pretty irrelevant to the problem isn't it like what do we do with this guy he's never going to collide with anybody it's just going to keep going in that direction living its best life but like nobody's ever going to catch up to it so from the beginning if we have somebody moving to the left that's fine doesn't matter but if there was suppose another robot here now I got a robot moving to the left and this time it matters because while we don't care about this one we don't care about this one this one is now moving to the right this one is moving to the left so if we get a robot moving to the left and the previous robot was moving to the right that's where there is a collision therefore you might get the idea of using a stack now among these two robots when they do Collide it's not going to be trivial because remember that each robot has some kind of health so at this point I think we can start going through this example and seeing how we can try to use a stack on it again assume we take the positions and we sort them so we're iterating through these in sorted order so let's say something like this two in this case this is the robot at position two if we sort this how are we going to be able to to get the health of that robot and the direction of that robot well the easiest way is just before we sort it just create a mapping for each robot take the position since we know the position is going to be unique we can use that as a key for a hash map of some sort and then we can create a mapping with that position mapping it to the original index and then we can use that index to get either the direction or the healths but this is kind of a small part of the solution just assume that we have a way to get the health of each robot and the direction of it for now let's just assume that so going through these in sorted order first robot two it's moving to the right it has health of 15 next robot at position three I guess I'll just kind of use this drawing because it's pretty good health 10 position three now these are moving to the right so if we have a stack here and I'm keeping track of it let's say I have two and I have three and these are both moving to the right we know if I add another robot that's moving to the right there's never a collision it doesn't matter if the previous robot is moving to the right or it's moving to the left if the current robot is moving to the right it's not going to collide with anybody to the left of it I think that's pretty self-explanatory right how could this guy collide with somebody on the left it's literally moving to the right that's pretty simple I think next we get the third robot it's moving to the left and that might be okay but the previous robot will check the top of the stack is moving to the right so we have the Collision now the question is how do we handle that Collision in the context of this problem they say the health is what matters so the health of this guy is a 10 as you can see over here the health of this guy is also 10 now if both robots have the same Health both robots will be destroyed now if the robot over here had more Health suppose it had 11 instead of 10 of course this robot is going to be the one that gets destroyed but you might think that the health is going to be updated by subtracting the health from this one like 11us 10 that's not the case actually if this robot got hit with another robot it collided with another robot that is we'd only subtract one regardless of the health of the other robot I thought that was kind of surprising but that's the context of the problem so we will go with it so in this case both of them have the same health so in this case what do we do well we decide never to add this one to the stack it never got added to the stack to begin with and this one got popped from the stack so um just pop it now imagine if it was slightly different just for the sake of arriving at the final solution look here if this was 11 this was 10 we get rid of this okay great but this one is still moving to the left and it looks to me that the top of the stack is still moving to the right so what I'm getting at is we might not just pop like if we get to a new robot a single robot might not just collide with one robot it might collide with multiple therefore when we are popping from the stack we're we're not going to need an if statement we're going to need a loop probably a while loop so just keep that in mind but anyways this got popped now we are at the final robot it is at this position we don't really care about the positions though notice that right we don't really do anything with the positions we're just using them to go through the robots in sorted order we do care about the health though and we also care about of course the top of the stack it's moving to the right this guy is moving to the left there's a collision therefore so this one the top of the stack has a high Health 15 so this one will never be pushed to the stack the way we're going to code this up is by popping this from the stack seeing its health is 15 subtracting that by one so now it's going to be 14 and then we're going to end up adding it back to the stack now I think we're pretty much ready to cat up the solution for a hard problem I think this one is somewhat approachable not saying it's easy don't be confused just because I can kind of make it look easy doesn't mean it necessarily is but in terms of complexity analysis recognize that we go through the inputs so we always knew it's going to be at least Big O of n but we did do some sorting beforehand so it's going to be an log in now the two data structures I'm going to use of course the stack and I mentioned earlier at the beginning that we are going to have some sort of mapping from the positions to the original indexes so that we can get the direction and health of each robot we'll do that before we sort the array now one tiny last thing that maybe I shouldn't mention immediately maybe I should save this for later but I think I want to just mention it now if we started with a robot that was going to the left didn't I say that that robot would never collide with anybody so I mean we could add it to the stack but there's no need to in the previous simulation I just ran we ended with one robot and the robot's Health was 14 what we want to return I should have probably mentioned is the health of each remaining robot but not only that we want to return it in relative order that the robots appear from left to right so if there's only one Rob robot it's just going to be 14 imagine there were two robots left imagine it was these two robots that are left we'd want their healths in relative order so 15 would go first 12 would go second this would be the output so that's something again we'll be able to do with the index map we'll just get all remaining robots that have a health that is greater than zero what I was getting at earlier is if I have a robot at the beginning the stack is empty and it's moving towards the left it's not colliding with anybody right now there before it's never going to collide with anybody so what I'm going to do is actually just not add it to the stack we can skip doing that it might seem like a small thing right now but it does make the code slightly easier I'll show you uh both variations just to prove it to you I want to quickly mention that before I started recording this video I was actually working on a python for coding interviews course I'm only showing this to you right now because I'm literally going to be using these techniques that I've been adding to this course like literally right now I'm going to be using several tips and tricks if you want to see all of them in one organized Place check out this this python for coding interviews course it'll be released in a couple days okay but getting into the solution remember how I said we were going to sort the input positions but before we sort it we want to have some mapping we want to preserve the original index of each position now we could do that with like a regular Loop but python has something called dictionary comprehension so we can actually do it in a oneliner so what I'm going to say is for I in range or actually I think there's a better way and I think I also cover this in my course so for IP in a enumerate uh the positions so this way we get the index and the position we want to map the position to the index so very clean nice code here can't really do this in most languages am I right now getting into the stack portion we're going to declare a stack it's initially going to be empty it's going to store the positions actually on second thought I did mention that the positions are never going to be used so it probably makes more sense to just store the indexes let's try this actually now I'm going to go through each position this we have have to do we have to go through the positions in sorted order and actually easier way to do this would be something like this if I just make this sorted so this will actually create a sorted copy but still we'll need uh this mapping up here we'll need to be able to map this position to its original index but now let's get the index cuz it's going to be needed um cuz we're going to be appending the index to the stack so let's use that index map we have up there now remember there were two cases the Direction that's what matters in this problem so so up above we can check using the string that was given to us if this is equal to R cuz if it's moving to the right it's not going to collide with anybody to the left doesn't matter what direction the robots to the left are moving in this is not going to collide with them so we can just go ahead and append it to the stack otherwise we got our robot moving to the left how do we know if it's going to collide with anybody well while the stack is non empty and while the direction of the robot at the top of the stack so let's get the top of the stack like this negative one of this stack so that's the index then we get the direction of it now if the top of the stack is moving to the right and remember our current robot is moving to the left cuz that's the else case then we want to start doing some stuff while this is the case so we don't know immediately here which one of the two robots has a larger health so we can't just do that in the if statement cuz there's going to be a bunch of arithmetic going on we're going to do that inside of the while loop cuz we might have to subtract from one of the healths so I'm going to in here I'm going to pop the top guy it's going to give us the index I'm going to call it I2 maybe I should call it J I don't know but anyways remember there are three potential cases one where the health of one robot let's call it I is greater than the health of the other robot and vice versa so else if and third find finally is when they are equal that's the simple case actually so I'm going to handle that first let's just set the health of it's called Health by the way in case you end up making that typo I really hope I don't make that typo here but I is equal to health of I two which is going to be equal to zero so both of them are set to zero the other two cases aren't too bad either suppose the health of the current robot is greater than the one that was previous to the left then the health of that robot I 2 can be set to zero it was destroyed but the first robot I is just going to be decremented by one it did collide with the other robot but it was not necessarily destroyed and it definitely wasn't destroyed because it has a larger Health than the other one so yeah we only decremented by one and we assume that this robot had at least a health of two cuz I think every health is going to be guaranteed to be positive now this case is going to be very similar I'm going to go ahead and copy and paste this so it's going to be the opposite so this one is going to be set to zero and I2 is going to be decremented and I should probably change the direction of this as well so this is when the other robot was larger so this robot was the one that got destroyed this is pretty close to the final solution maybe this is what makes it a hard problem it's kind of subtle but we're missing something here imagine we have some robots moving to the right like this and then we get a robot that moves to the left this one suppose both of them Collide suppose both of them are destroyed that's very simple right it looks like our code is going to handle that cuz this guy gets popped and I don't think i1 ever gets added in this case right now so that case is simple but what about the other case what about when the left one gets destroyed well it looks like our thing is kind of handling that too this one is going to get destroyed our Loop is going to keep going because the top is still moving to the right but what if we deleted all of them well in that case after all of this is set and done when the loop is finished down here we should say something like if heals of I is greater than zero in Python you can just say if heals of I if that's the case let's go ahead and append it right at the end so here we'll go ahead and append index I now we handled that case but there's one other one that we did not handle actually so these two Collide suppose this one gets destroyed boom this one stayed alive what are we missing in this code well that case was right here the top of the stack was bigger so the current robot got destroyed well we popped the robot to the left right we moved this off of the stack we should probably add it back to the stack if this is the case so in that if statement I'm going to say this one was destroyed this one stayed alive go ahead and add I2 back to the stack so here I'm going to say append I2 okay beautiful we're almost done now but again we're kind of missing something something if this robot got destroyed our Loop isn't necessarily going to stop but we want it to stop right our current robot which was the one that was uh moving to the left it was the one that got destroyed and there still might be some other robots left well how do we know if that's the case it's pretty easy We'll add another condition to our Loop we'll say and health of I is greater than zero or we can just say healths of I so now we find have pretty much everything right at the end what we want to return is the healths of the robots and we want to do it in relative order so let me do something clever kind of like how I did up above dictionary comprehension I can do list comprehension down here so for every Health in healths I'm going through these in order notice that if the health of a robot is greater than zero notice that we did modify the healths as we went so we'll know if they were set to zero if it's greater than Z then let's add it to the list so I can do something very clean one line like this isn't python amazing so I'm going to run this now as you can see it works it's pretty efficient there's just one little it's not an optimization I just want to kind of clean up the code a tiny bit remember how this else case is the case where a robot is moving to the left right so like I kind of showed in the comments something like this like our current robot is the one moving to the left in what what case would this if statement execute in which case would this Loop terminate and the health of the current robot was still greater than zero only if it collided with all the previous people and destroyed them and still stayed alive okay what's so special about that case well now it's never going to collide with anybody again right it's moving to the left I don't see how it would ever collide with anybody everybody has already been destroyed so we don't need this if statement down here I'm going to get rid of it and I'm going to go one step further if I remove that if statement I'm basically saying we're never going to have robots moving to the left from the beginning of the stack okay so we're only going to begin with robots moving to the right that makes sense to me and then if there is a robot moving to the left it will either be destroyed or it will destroy all the other robots like this right or it will be destroyed maybe taking out some of the other robots in the process but either way our stack will look like this what I'm getting at is we don't need this right here we know if the stack is nonempty the top of the stack is always moving to the right in other words every robot on the stack is moving to the right why would we have a robot moving to the left I mean I guess we could have a case like this but why would we have that like I said we don't want anything beginning that's moving to the left so what I'm getting at is just get rid of this here as well not a big optimization or anything but it does make the solution a little bit cleaner I'm going to go ahead and run this as well and see it also works I guess it's more efficient this time but please don't pay attention to this stuff it's pretty useless if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon