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.

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.

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.

Here there is my solution: https://ideone.com/jQusfi it constructs kind of a graph (for the people who requested the graph approach), although it's not necessary to build a real graph once considered the constraints of the problem.

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()).

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.

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; }

Do we need to just check whether its possible to go to other side , or we have to give a clear cut path . I havnt seen full video , just saw the question part

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; }

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….

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)? :/

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];

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.

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

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.

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.

– 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.

On LeetCode: https://leetcode.com/problems/jump-game/

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.

1) You've forgot to write `next_step` function.

2) I reckon your approach is called "greedy", not "simple".

Why don't you make such more videos? Btw thanks alot

Your videos are just amazing.love from india.

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]));

Is this a fuel charging problem?

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

}

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

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

guys, what is the time complexity of the simple solution?

Here there is my solution: https://ideone.com/jQusfi

it constructs kind of a graph (for the people who requested the graph approach), although it's not necessary to build a real graph once considered the constraints of the problem.

def is_hoppable(lst):

length = len(lst) #length of list

l = 1

for i in lst:

if(i > length-l):

return True

l += 1

return False

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()).

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;

}

}

Is the simple approach faster than the dynamic?

Can you jump over a "tower" with a greater height than your current tower?

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))

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.

This is same as : https://www.geeksforgeeks.org/minimum-number-jumps-reach-endset-2on-solution/ ?

According to your question "just hop out of the array"…. hop( array.length+1) Done!

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;

}

Please make this type of video as soon as you can. By the way we love your videos. Love From India.

Do we need to just check whether its possible to go to other side , or we have to give a clear cut path . I havnt seen full video , just saw the question part

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;

}

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….

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)? :/

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);

}

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.

#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

function hop(int index)

{

if ( index > n-1)

print "yes";

for(int step=1; step <= array [index] ; step ++ )

hop ( step + index );

}

Is this correct?

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.

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

Where is the code for the next_step() method ?

DIdnt get this !

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.

The next step function is almost like a derivative. We look at how much the change allows us to change.

Your approach fails for [4, 3, 0, 3, 1, 0]

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

this could've been solved using backtracking approach as well or not ?

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.

Next_step() function ??

Why can't you come with android app for those videos

– 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.

Can someone write the next_step function plssss