Coding Interview Question: Tower Hopper Problem

Key Takeaways

here's one of my favorite coding INB problems that I've seen so far and I'm going to call it the tower Hopper problem here and here's the problem you're given an array of integers and each integer in this array represents the height of the tower in that position so with this given array we have six towers with the heights 420 02 and zero and the numbers you see at the top are just the indexes for the towers and here's the objective of this problem you start at index zero just imagine you're standing on this Tower at index zero of height four and you're going to jump from this Tower to another Tower to another Tower and eventually we want to see if there's any way to get to the end of the array or to be precise to outside of this array and the amount of steps that you can jump over depends on the height of the tower that you're standing on so for example if you're standing on the first Tower at inex Z because the height is four you're able to jump over four steps at most so at most you can choose to jump over to index 4 or you can choose to jump over to anything less than that so either index one two or three whatever Next Step that you choose you're going to repeat the same process so so for example if you choose to go to index one after index zero you have a choice between jumping over to index 3 or index two because the height of this Tower is two so the maximum number of steps that you can jump is two and in this particular example you can jump from index zero the starting point to index 4 by jumping over four steps which is the maximum steps that's allowed for this Tower and then jump from there to outside of this array by jumping over two steps and note here that if you jump just one step and get to index 5 then that wouldn't clear the requirement because our goal is to get outside of this array and not just to the end of the array now to formalize this problem a little bit what we want to do is we want to be able to write a function called is able which takes the given array and returns true if it's possible to start at index zero and hop from one Tower to another and eventually get outside of this array as we saw earlier is HPP of this Towers should return true but is poppable of one Z should return false because with this particular set of towers the only choice here is to start at index zero and then hop to index one and from there we won't be able to hop anywhere because the height of that Tower is zero now as usual if you want to practice pause the video right here and see if you can solve the problem and come back to the video when you're done or stuck there are few potential solutions for this problem and one of them is using a graph we can look at each Tower as a node in our graph and each path each potential path from one Tower to another as an edge between these nodes and using these we can construct a graph that represents the towers and the paths between them and the objective in this solution will be to find a path from the first node or the first Tower of height four at index Z to the outside of this array and the outside of this array can be represented as one of the nodes once we have that we just need to use breast first search or dep first search to find at least one PA to see if we can get from the first node to outside of this array another potential solution to this problem is a dynamic programming or a recursive approach if you look at the original problem of writing is helpable it's a hard problem it seems like a hard problem so the idea behind a dynamic programming or recursive approach is to break it down into smaller problems and then solve those instead so we'll try to write a function called helper which takes two arguments Towers which is the same as the original towers and an index value or an integer value which represents the starting index and helper of towers and the starting index should return true if it's possible to start at the given index in this case index four and hop from this Tower to maybe another Tower to another Tower and eventually get outside of this array in this particular case this should return true because it's obvious that we can hop Two Steps From index 4 and get outside of this array and the idea of this approach is to write is helpable by recursively calling the helper function I'm not going to go into too much detail here but for example if we already know that the return value for helper of towers and four should be true it's going to be easy for us easier at least for us to find the return value for helper of towers and zero this is asking ourselves is it possible for us to start at index zero and then hop to another Tower maybe another Tower and eventually get outside of this array so this is a equivalent to is H of towers and right away we'll know that it's possible for us to go from index zero to index four just by hopping because the maximum number of steps that we can hop from this Tower is four and since we already know that it's possible for us to go from index 4 to outside of this array from helper of towers 4 we'll know that helper of towers and zero should be also true now both of these approaches work the graph approach and the dynamic programming or recursive approach but my favorite solution to this problem is neither of these I'm not sure what I should call this so I'm just going to call it the simple approach here here's how it works we're going to try to write a function called Next Step which takes two arguments the first argument being the current position that you're standing on and the second argument is the same towers as the original given Towers and this should return the next optimal step given the current position so for example the next step of zero and Towers this particular Towers should return four because the optimal next step is index four and that next optimal step will be the next current position and we can just feed it back to the next step function to find the next optimal step after that so in this particular example we're going to feed four back into the next step function to find the next optimal step after that and next step of four and Towers or the optimal step for index 4 for this particular Towers should return six because after index 4 we'll be able to just jump two steps ahead to get outside of this array and we're done and whatever is outside of this array can be denoted in this case with index six or in general with the length of the array as the index so how should we write this function next step the idea of this function is going to be we look at the starting index in this particular case zero and we'll ask ourselves what's the next step after that that'll allow us to go the farthest in the next step after that step so for example from index zero we could jump one step ahead to choose index one and in that case we'll be able to go up onto index 3 by jumping two steps ahead from index one if we choose index 2 we're stuck on index two because the height of this Tower is zero and if you choose index 3 it's the same we're stuck on index 3 and if we choose index 4 we'll be able to go two steps ahead by jumping Two Steps from there and we'll be able to get to index six at most so in this particular case we'll choose index 4 as the next optimal step because that's the next step after zero that'll allow us to go the farthest in two steps so why is that one the optimal next step after index zero here's one way to think about it if you choose index 4 as the next step the range of indices that we are covering ranges from 0 through six and if you choose for for example one in this instead index one instead as the next step the range of indexes that we can cover ranges only from zero through three instead so the range that we can cover with index one as the next step is merely a subset of the range that we can cover with index 4 as the next step now it's possible in certain situations that whether we choose index one or index 4 we'll be able to get to the end of the array anyway but if it is the case that it's possible for us to choose index one and get to the end of the array it must also be true for us to be able to choose index 4 and then hop to another Tower another Tower and eventually get to the end of the array and this is why the next optimal step after the current position is the position from which we can go the farthest in a single jump just to clarify this point a little bit more let's examine another example as you can see we have towers of the heights 13 53 1 and so on and we're trying to determine what the next optimal step should be let's say from index one so we're going to call our function next step of one and towers and as we saw earlier to find the next optimal step after that we need to find the next step from which we can go the farthest in a single jump and since we have a tower of height three we have three potential choices if we choose index two as the next optimal step or as the next step we'll be able to jump five steps ahead of it since the height of this Tower is five so we'll be able to get to index 7 after that if we choose index 3 as the next step we'll be able to get to index 6 and if we choose index 4 we will only be able to get to index 5 after this and if you examine the ranges that we can cover with index 3 or index 4 as the next step are merely subsets of the range that we can cover by choosing index 2 as the next step so the next optimal step after index one is two once we have the next step function written writing out the rest of the algorithm for the isable function that we wanted to write originally should be easy in this function we'll first set a local variable called current to zero and we're going to use this variable to keep track of where we are standing on currently and we always start at index zero after that we'll feed the current number to The Next Step function to find the next optimal step in this particular case the next optimal step is the index four and we'll update current to that number so current will be four and we'll just keep repeating this process until we get to either outside of this array in that case we should return true from this function as we do in this example or we fall into one of these cells where the tower's height is zero in that case we won't be able to hop anywhere else from there so we'll need to return false from this function let's see what this solution might look like in code we're going to write a function is stable which takes towers and returns true of course if it's possible to start at index zero and then hop over this Towers these towers and get to the end of the array or to be precise to outside of this array the first thing we're going to do in this function is we're going to set as I said a local variable called current to zero and we're going to use this variable to keep track of the current position and then we're going to run a w Loop and in this W Loop will update the current position to the next optimal step given the current position and if the current position happens to be larger than the length of towers or equal to the length of the towers then that means that the current position is already outside of this array so we return true and then if that's not the case and if the current tower has the height zero for example this one that will mean that we'll forever be stuck there because we won't be able to help anywhere else from there so we'll return false in this condition that's it for this video thanks for watching and I'll see you in the next one