Design Browser History - Leetcode 1472 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem design browser history we're given a single browser Tab and we want to basically simulate the behavior of navigating between browser Pages we know that a page is represented with a URL and we will be having some starting home page for us that will be provided to us and we'll take care of that in the Constructor now there's three main operations that we want to support one is pretty simple we want to visit a particular URL of course you can do that with a browser so suppose that a is our home page then we can visit another page let's say B is the page that's provided then we end up on a second page now the interesting thing here is that we have two more operations where we can move back and we can move forward in the browser history similar to how you can do it with a real browser we know that if we navigated from A to B we can always move backwards and if we do that we end up at this page at the previous page and if we do that we can also move forward in the browser history and then maybe after we move forward we can navigate to a new page like C and just to clarify the back and forward operations are not just done by moving One Step suppose we're at B we can move one step and go to C and then from C we can move one step and go to B but we could also being at C we can move two spots back to a we can move an arbitrary number of steps either backwards or forward a couple quick edge cases imagine we are at C and the number of steps provided for us to move backwards is two well we would move to a but what happens if the value is three what happens if we try to move three steps backwards well we end up know where we end up out of bound so if we're given a value that's too large then we just move as much as we can we tried to move three spots but we couldn't so we just moved 2 two spots instead and got back to the beginning that's pretty simple and the same thing would happen if we were at a and we wanted to move three spots forward Well we'd be out of bounds so instead we just move as much as we can we move two spots and then end up at C so I think that's not too complicated now there's one last Edge case well not really Edge case it's more about the main behavior of the visit operation suppose we are at position a we're at this page we know we have our portion of forward history but what happens if from here we try to move to a different page like d well then we end up at D now we should be able to move backwards to a which we can but we can't really move forward anymore because this was kind of a different branch of our history we can't really go back here and just like in a real browser we want this to simulate that so what happens is all of the forward history at this point when we visited a new page is cleared so all of this is gone and that's pretty much the main behavior that we're going for with this problem now there are two main ways of solving this problem one is kind of like I'm showing with a linked list because as you can tell we want to be able to move in both directions so we want to be able to move forward which you can with a singly linked list but we also want to be able to move backwards which you can with a doubly linked list so that's how I'm going to be implementing this solution it's pretty rare that we get to use a doubly linked list so I think now is a good opportunity to do so but I want to mention that we can also solve this problem with a stack or a dynamic array and I'll touch upon that at the end that's actually the more efficient way to solve this problem and very quickly I want to mention what would the time complexity be for each of these operations if we did it with a linked list well how exactly would we Implement each of them as you could tell the visit operation is pretty much always going to be constant time because no matter where we're at whether we're all the way at the beginning of our history or at the end it doesn't matter because we're visiting a page anytime we visit a page all we really have to do is say okay the next note after this current node that I'm at is going to be whatever the new page happens to be in this case maybe it's D that's always going to be easy now the less efficient operations are going to be these two where we have to move backwards or forwards with a linked list we can't just index a random position like we can with an array that's a downside of this approach because if we want to move backwards or forwards depending on the number of steps this could be arbitrarily long so this is an of n time operation where n is the size of the doubly linked list because we might have to Traverse the entire list if we were to implement this with an array we would actually be able to get each of these operations down to constant time which I'll show you at the end okay so now let's code it up the first thing I want to do is create a linked list node class so I'm going to create a class called list node it's going to have three Fields a value which is going to be the string for the URL that we're currently at we're also going to two pointers a next pointer well this is the previous pointer and a next pointer and by default these two pointers are going to be set to null so now to initialize our browser history I'm going to create a current pointer for whatever current page we happen to be at I'm going to create a list node I'm going to pass in the home page as the value and I'm not going to pass anything in for the previous or next node because that can just be set to null now let's move on to visit which is pretty straightforward what we want to do is create a new list node for this URL that we're given we're going to just pass in the URL and before I get to the previous and next pointers what are we doing with this node well we know we're currently at self.car we know our current node is not going to be null because we did initialize it with a home page and we know that whenever we move back we're never going to go out of bounds so we can pretty much assume that our current pointer is never going to be null so what we're going to do is say our next pointer for current is now going to point at this new node that we just created it so what we can say is that our next pointer is going to point at whatever new node that we just created is since we are creating a doubly linked list we also want this new node to point back at the current node so we want the previous pointer of this new node to point at Curve so what am I going to do I'm going to say previous should be self dot her and I'm not going to pass anything in for the next pointer because it just needs to be null anyway because this new list note is going to be the last node in our linked list now also since this is the last note and this is also the current node we can set self.cur equal to self.cur dot next so not too bad there now we also have the back operation so while our parent pointer is non-null and steps is greater than zero we want to set self.cur equal to self dot Cur dot previous because we're moving backwards this many steps we should also decrement the number number of steps we're going to keep moving backward as much as we can until we've either moved back this many steps or we somehow ended up out of bounds but remember we never want to end up out of bounds instead of letting self.cur somehow equal null we should instead say while self dot Cur dot previous is non-null this way we will end up stopping as soon as we reach the last node if we see that the previous node is null that means we reached the last node that we could move to or at least the first node since we're moving backwards and once that is done we want to return self dot Cur dot val this part kind of tripped me up because I forgot we actually had to return a value here but we do we have to return the value that we ended up moving backwards to the forward operation thankfully is pretty much the exact same as this except we're going to be moving in the other direction so I'm going to go ahead and copy and paste this and instead of looking at the previous node we'll be looking at the next node and steps we'll still be decremented by one but instead of moving backwards we're going to be moving forward and that is pretty much it so now let's run the code to make sure that it works and as you can see yes it does and it is pretty efficient beating 69 there's actually a more efficient solution let me quickly show that to you I mentioned that there's a solution using an array and this is that solution we're actually using an array slash a stack so we don't need a linked list our self.history is going to be equal to an array with just a single value which is the home page initially we also have two pointers one I'm calling I but you could consider it our current pointer the same as we had for our previous solution so this is going to be pointing at the current page that we're currently at we also have a variable to maintain the current length the reason I have a separate variable for this and we can't just take the length of our current array is because this pointer is actually going to be the true length or at least the length that we consider to be the real length we don't consider the length of this array and you'll see what I mean in just a second now I'm going to start with the back and forward operations first because they're actually more simple of course if we have an array and we want to move backward this many steps we don't have to shift a pointer because with arrays we can just calculate the new position we know that I is our current position so if we take I and subtract the number of steps we will have the new index but the problem is this could be out of bounds so what we need to do is have an if statement to make sure that this is not less than zero now an easier way to do that is to just take the maximum of whatever this happens to be maybe it's bigger than zero or maybe it's less than zero if it's less than zero this equation this operation will be set to zero if this is greater than zero self.i will be set to whatever value this happens to be and then we just take that pointer and return self.history notice how moving backwards does not change the length of our array because moving backwards does not delete anything same as moving forward we do not delete anything we're doing pretty much the same thing self.i except we're adding the number of steps instead of taking the maximum we're taking the minimum because we don't want this value to go out of bounds in the other direction we don't want this to be greater than self dot length minus one this is our length variable I'm not taking the length of History you'll see why I'm doing that when we look at the visit operation above in summary this forward operation is almost exactly the same as the backwards operation now this is where the actual complexity comes from well there's not much complexity but these both were constant time operations clearly we're just indexing an array and this is the same thing clearly we just have a couple conditionals and we are just you know doing basic operations and indexing an array or appending to an array all of these are constant time operations but what are we doing here well remember when we visit a URL we're pretty much erasing the forward hist history but if we actually manually erase the forward history like we pop every value from this self.history stack or array we could do that but the problem is that that would end up being an O of n time operation we actually don't need to do that we don't need to delete those values we can sort of soft delete them what I mean is first we know we need to add this URL to the next position by next position I mean the index I plus one so that's what we're going to do we can only do that if that position has already been filled before because otherwise we're going to get an index out of Bounce error so I first make sure that the array self.history is long enough initially it won't be long enough to insert at the index 1 position so we have to make sure that it is and if it is then we do this otherwise we append we can't just Index this because we'll get out of bounds error but that's pretty much it and then once we do that all we have to do is increment our eye pointer because we're now at the next position and we set our length equal to I plus one that's just kind of how you know math works for arrays that are indexed starting at zero and that's pretty much it the reason we're then updating ourself.length is because of this forward operation basically when we set this equal to I plus 1 before that it will probably be equal to some bigger value before that it may be equal to an even larger value like for example if we have some values 1 2 3 and 4 but our current position happens to be over here at a two then and we want to insert a new value something like 5 maybe then we'll insert that 5 over here at the same time we want this forward history to be deleted instead of manually deleting it we'll just be updating a pointer instead so that we consider this value to no longer be there even though it is taking up memory still so that's basically how we can get this to be the most optimal solution I admit that this code might not be super easy to understand especially if you're a beginner and that's because I'm kind of using some tricks that you might not be used to yet it's okay if you have to kind of write out longer code you have to write out some if statements here and here and maybe even the first time you solve this problem you do have to write it a less efficient way or a different way or maybe you just have some bugs that's okay but I did want to show you the most optimal solution if this was helpful please like And subscribe if you'd like to see the code in a language other than python you can check out neatco.io thanks for watching and hopefully I'll see you pretty soon