43 thoughts on “Coding Interview Question: Tower Hopper Problem

  1. The next_step() approach is called a brut-force approach
    In fact, this is simple, but very inefficient in case of very high towers and very long arrays. Particularly, in case of tower with high n, will take n trials until getting the optimal solution only for the first jump. Brut-force solution is always easy but mostly with really bad time complexity. In this particular case, the DP method works with O(n) time complexity, while brut-force approach takes it in O(n^2), which is too inefficient solution.

  2. My brute force solution. I will try to optimize this;

    function canHop(arr) {
    if (arr[0] >= arr.length) {
    return true;
    }
    if (arr[0] == 0) {
    return false;
    }
    for (let i = 0; i < arr[0]; i++) {
    let subArr = arr.slice(i + 1);
    let done = canHop(subArr);
    if (done) {
    return true;
    }
    }
    return false;
    }

    console.log(canHop([4, 2, 0, 0, 2, 0]));
    console.log(canHop([1, 0]));
    console.log(canHop([1, 1]));
    console.log(canHop([0]));
    console.log(canHop([3, 0, 0, 1, 2, 0, 2, 0]));

  3. It seems to me that if you were to go left to right through the array and keep track of the current highest available amount of steps forward while checking for 0 and subtracting from the current highest 1 for every move forward, then you can just disprove false or break at false. It also gets rid of trying to see what the best next hop is. This should be just as optimal as finding next best hop without having to understand how to find next best hop. I can't think of an implementation of next best hop that would contain fewer operations than O(n). Here it is in powershell.

    Function Can-IGetOut{

    param($towers = @())

    $previousMaxDistance = 0

    foreach($tower in $towers){

    $previousMaxDistance -= 1

    if($tower -gt $previousMaxDistance){

    $previousMaxDistance = $tower

    }

    if($previousMaxDistance -eq 0){

    return $false

    }

    }

    return $true

    }

  4. it begins from the end and checks if last tower is at least 1 block height. It is it saves that tower as checkpoint if last tower is at least 1 block height ,and does the same thing again. if last tower isn't at least 1 block height then it checks if the last but one tower is at least 2 block height. at the end if first tower saved as checkpoint then result is true and if it's not false.

    ———————————————————————-

    def is_hoppable(array):

    length = len(array)-1

    array += [0]

    checkpoint = length

    i = 1

    while True:

    if (array[checkpoint – i] >= i):

    checkpoint = checkpoint-i

    i = 0

    if (checkpoint == 0):

    return True

    elif (checkpoint == i):

    return False

    i+= 1

    ——————————————————————————

  5. Here is my solution:

    int current = towers.size();
    for (int i=towers.size()-1;i>=0;i–){
    if (towers[i] >= current -i) current =i;
    }
    if (current != 0) return false;
    return true;

    It won't make minimum number of hops, but it gives the right answer and it is O(towers.size()).

  6. Hi Everyone, I wrote a simple code to solve this problem. Can anyone validate and let me know is this a better approach?

    let a = [4,2,0,0,2,0];
    flag = -1;
    output = 0;
    for(let i =a.length;i>0;i–){
    if(a[i]+i>a.length && flag==-1)
    {
    flag = i;continue;
    }
    if(a[i]>=flag && flag!=-1){
    output = 1;
    }
    }

  7. I've done this in like 5 minutes tops, can anybody give me feedback please ? 🙂

    towers = [4,0,0,2,0]

    towers2 = [1,3,5,3,1]

    def jump(lst):

    arr = []

    for i in range(len(lst)):

    arr.append(False)

    for i in range(len(lst)):

    if lst[i] > len(lst)-1-i:

    arr[i] = True

    ##FOR CLARITY PURPOSES

    print(arr)

    if arr[0]:

    return True

    else:

    for i in range(len(lst)):

    if arr[i]:

    return jump(lst[:i])

    return False

    print(jump(towers))

  8. Hi, I like your approach to solve a problem. Can you also make a video to solve "Largest rectangle area in histogram" problem. I saw many videos, but I am not really clear about that. Then I felt you might be the right guy. Thanks.

  9. Just keep a count of the maximum distance you can travel from your current index and iterate for that length. If you encounter an index which increases that distance, increase your count and continue until it is greater than the array length, or until you reach the end of that distance. O(n)

    for (int i = 0; i < arr.Length; i++) {
    if (max >= arr.Length) return true;
    max = Math.Max(arr[i] + i, max);
    if (max <= i) return false;
    }

  10. If you want to use greedy solution, it's easier to understand if you start from the end index, and greedy always give you correct result in this case.
    find the right-most tower that can reach to your destination e and update e, why always find the right-most tower? food for thought.
    public boolean canHop(int[] nums) {
    int n = nums.length;
    int s = n-1;
    int e = n;
    while(s >= 0){
    if(s+nums[s] >= e){
    e = s;
    }
    s -= 1;
    }
    return e == 0;
    }

  11. Hey YK, thanks for the analysis. Can you please explain in anothe video with more detail the next_step function…. For me that function seems is the tricky part….

  12. Can't find it anywhere here… What's the Big O complexity of recursive/recursive+DP/"simple"?
    Am I right assuming recursive is O(m^n) where m is the maximum height, recursive+DP is O(n) and "simple" is the same O(n)? :/

  13. Ended up with this algo below. I'd love to get considerations or optimizations.

    The idea is always jumping to the farthest tower on each jump considering the position of the tower we are evaluating.
    So in his example, there'd be a tie between tower 1 and tower 4 because they're both height 2. BUT tower 4 is bringing the jump to tower 6 (in this scenario, out of bounds – so return true)

    public boolean isHoppable(int[] towers) {

    int lastHop = nextHop(towers, 0);

    return lastHop >= towers.length;
    }

    public int nextHop(int[] towers, int tower) {
    int currentHop = tower + towers[tower];
    int maxHop = 0;

    if (currentHop >= towers.length) {
    return currentHop;
    }

    for (int i = tower+1; i <= currentHop; i++) {
    int hop = i + towers[i];

    if (hop >= towers.length) {
    return hop;
    }

    if (hop > maxHop) {
    maxHop = hop;
    }
    }

    if (towers[maxHop] == 0) {
    return 0;
    }

    return nextHop(towers, maxHop);

    }

  14. The true greedy approach sorts all the distances from the goal and then it takes the furthest element back to the start as long as it's feasible. Runtime is O(N log N) though which is worse than DP.

  15. #My python implementation!

    def is_hoppable(buildings):
    #buildings = [4,2,0,0,2,0]
    jumps_needed = 1
    for i in range(len(buildings),1,-1):
    if buildings[i-1] < jumps_needed:
    jumps_needed += 1
    else:
    jumps_needed = 1
    if jumps_needed > buildings[0]:
    return False
    else:
    return True

  16. I am not sure, that "simple algorithm" work.

    Imagine this towers [4,2,0,3,1,0].
    next_step(0,tower) = 4.
    next_step(4,tower) = 5.

    but
    next_step(1, tower) = 6

    and solution is to use tower 0,1,3, out.

  17. Python implementation of recursive solution:
    def helper(arr, index):
    if arr[index] == 0:
    return 0
    end_index = index + arr[index]
    if end_index >= len(arr):
    return 1
    result = 0
    for i in range(index + 1, end_index + 1):
    result += helper(arr, i)
    return result

    def is_hoppable(arr):
    if helper(arr,0) > 0:
    return True
    else:
    return False

  18. Hey CS Dojo I have a doubt on your simple solution. I just checked a random case 4,2,0,4,1,0,1 . In this case there can be a solution by jumping form first tower to 4th tower and then from there jumping to outside but by your method when I've traced it, I'm getting false but actually I have a way to go out. Please clarify my doubt.

  19. It's my solution in Python. Complexity: O(n). Code:
    def is_hoppable(towers):
    target_idx = len(towers)

    for idx in reversed(xrange(0, target_idx)):
    tower = towers[idx]
    tower_range_idx = idx + tower

    if tower_range_idx >= target_idx:
    target_idx = idx

    if target_idx == 0:
    return True

    return False

  20. Go right to left. Keep track of minimum distance needed to escape. Each time you find a tower that meets that minimum distance, set the distance to 0 and keep going. If the left-most tower meets the distance, return true. 1 pass, O(n) time O(1) space. No fancy stuff needed.

  21. – Have an endpoint variable initialised as the index of the position after the last element.
    – Loop from end to start of array.
    – For each element, if (height + current position index – 1st position index) >= endpoint, assign that index to endpoint.
    – At end of loop, if endpoint is at first index, return true. Otherwise, return false.

Leave a Reply

Your email address will not be published. Required fields are marked *