Just spent an hour yesterday trying to solve this exact problem and couldn’t get it. Hopefully one day I’ll be experienced enough to be able to make stuff like this look as easy as you do
This works because we are given a _max_ jump length, not a fixed one. So anytime we can get to a goal from another space, any solution that jumps over that space could choose not to and just land there. So, once we've determined that we have a path to the goal from some spot, whether or not there is a path to that goal is _equivalent_ to whether or not there is a path to the final goal. But if we can _only_ jump the number at that point (or there is some other restriction to how we can jump), this may not be true, as it may be that all possible paths to the end goal skip over some node from which you could reach the goal.
Thanks for the video! I think you could do it starting at the beginning and also consider values of 0 in the array which could cause an infinite loop def canJump: i = 0 while(i = len(nums) or nums[i] == 0: return False return False
Why don’t you look for the 0 in your array and count the distance to this index and check wether your key at that index is larger than the distance to the 0?
This is what I did, starting from the 0'th index check if you have still moves left , if yes then move forward and update the moves: bool canJump(vector& nums) { int n=nums.size();
int i=0; int posi=1; while(posi!=0) { if(i==n-1)return true; posi--; posi=max(posi,nums[i]); i++; } return false; }
I also thought to start from the beginning and move forward, and thought I'd do it differently than he did, I think it's the same, computationally it should give same results and performance, if you don't screw up the algorithm of course
Yea I got the same question. Since he can start from 0. In the for loop he can read the element value to fast forward the i value. And if it reaches the last element of the array just return true
You can't really go forward because it's "MaxJumps" so you can jump fewer and thus would have several available jump positions per index that you need to follow. Backwards makes sure that you can reach the end via any route.
Not only can you go forward, but it'll be even faster than "backwards" algorithm. Basically you calculate maximal reacheble index from each position while keeping global max reach. Something like that: i = 0 max_i = arr[i] while ++i = len - 1 return true return false
Consider an array that is [5,100,1,1,1,1,1,1,0,0,0,0,0,0,0,1] You can't just blindly add on the found element at the index as you'd likely get caught in a trap. In the array you would add on the 5 and skip over the 100 trapping you behind the zeros as there is only single jumps remaining.
Solution's fine, but if I were the interviewer I'd have complained about that final if-else block, which is a "clean code red flag". How to properly do it: `return goal == 0;`
I feel like this a bad solution because while it works, it doesn't follow the instructions of the question which is to start at the array's first index. You could solve this as well by initializing a variable at 0 that is the current furthest index you can reach in the array. Then using a for loop (i) with range 0 to n-1 and incrementing by 1, you can set the furthest as the max() of the current furthest index or i + nums[i]. At that point while still in the loop you can check to see if the furthest index is equal to the current index i and return False if they are equal. If you get through the loop you can return True.
The "start at index 0" refers to where the jumping sequence starts, not where your program must start. The program is not the jumping sequence, the program is a feasibility check
Idk but this code looks weird. And it also possible that it loops endlessly. I'm not exactly sure though. Also max jump, doesn't it mean, you can also jump lower than the max jump?
Seems like your algorithm is not correct. Try array [2,3,0,4]. His algorithm will return true, but, as far as I can see, yours will return false at second step inside while.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Thank you RUclips for recommending these types of videos
Just spent an hour yesterday trying to solve this exact problem and couldn’t get it. Hopefully one day I’ll be experienced enough to be able to make stuff like this look as easy as you do
Lmao same, I was just looking for zeros and see if any element to it's left has more value than it's position w.r.t zero
@@pickaboo1697ayoo i was trying exactly same thing.... Tf
You've got this :)
Ask step bro.
Ohh yes, the classic if ....: return True else: return False
return goal == 0
I honestly had the intuition on what you did. But I couldn't write the logic so fluently. Thanks for the video and the inspiration ❤️
That's amazing :)
This works because we are given a _max_ jump length, not a fixed one. So anytime we can get to a goal from another space, any solution that jumps over that space could choose not to and just land there. So, once we've determined that we have a path to the goal from some spot, whether or not there is a path to that goal is _equivalent_ to whether or not there is a path to the final goal.
But if we can _only_ jump the number at that point (or there is some other restriction to how we can jump), this may not be true, as it may be that all possible paths to the end goal skip over some node from which you could reach the goal.
Thanks for the video! I think you could do it starting at the beginning and also consider values of 0 in the array which could cause an infinite loop
def canJump:
i = 0
while(i = len(nums) or nums[i] == 0:
return False
return False
Did you test this?
Why don’t you look for the 0 in your array and count the distance to this index and check wether your key at that index is larger than the distance to the 0?
This sounds like a cool solution
and what if there are multiple zeros?
@@mazthespaz1 you do that for every zero
@@emilfrei6303 code it. let's see it. seems like you can make it work, but will not be as efficient. prove me wrong
Looks DP enough 😅, o(n) is also workable
Yep!
This is what I did, starting from the 0'th index check if you have still moves left , if yes then move forward and update the moves:
bool canJump(vector& nums) {
int n=nums.size();
int i=0;
int posi=1;
while(posi!=0)
{
if(i==n-1)return true;
posi--;
posi=max(posi,nums[i]);
i++;
}
return false;
}
Why not res := len(arr) % arr[0] ; if res != 0 { return false } else { return true } ?
How's this faster/easier than going forward?
I also thought to start from the beginning and move forward, and thought I'd do it differently than he did, I think it's the same, computationally it should give same results and performance, if you don't screw up the algorithm of course
Yea I got the same question. Since he can start from 0. In the for loop he can read the element value to fast forward the i value. And if it reaches the last element of the array just return true
You can't really go forward because it's "MaxJumps" so you can jump fewer and thus would have several available jump positions per index that you need to follow.
Backwards makes sure that you can reach the end via any route.
Not only can you go forward, but it'll be even faster than "backwards" algorithm. Basically you calculate maximal reacheble index from each position while keeping global max reach. Something like that:
i = 0
max_i = arr[i]
while ++i = len - 1
return true
return false
Consider an array that is
[5,100,1,1,1,1,1,1,0,0,0,0,0,0,0,1]
You can't just blindly add on the found element at the index as you'd likely get caught in a trap.
In the array you would add on the 5 and skip over the 100 trapping you behind the zeros as there is only single jumps remaining.
Would a greedy algorithm still work if you had to return the shortest path?
Sort of. You could do a linear BFS-ish solution by noticing that the shortest distance and monotonic and increasing by 1 at max
Solution's fine, but if I were the interviewer I'd have complained about that final if-else block, which is a "clean code red flag".
How to properly do it: `return goal == 0;`
Yeah I wrote this on purpose to try and make it clearer for some folks but I think it just backfired lol
Sir,what if the array have [2,2,2,4]?
It returns true
this guy reminds me of my ex boss.. he used to do insanely complex things where solution was super simple
What the fuck is he doing bragging about a 56th percentile solution
It would be much faster given larger values of N
Should you not start the iteration from n-2?
I suspect you could also do that yes
Dint have time
I can't understand this someone help please😭
what even?
I feel like this a bad solution because while it works, it doesn't follow the instructions of the question which is to start at the array's first index.
You could solve this as well by initializing a variable at 0 that is the current furthest index you can reach in the array. Then using a for loop (i) with range 0 to n-1 and incrementing by 1, you can set the furthest as the max() of the current furthest index or i + nums[i]. At that point while still in the loop you can check to see if the furthest index is equal to the current index i and return False if they are equal. If you get through the loop you can return True.
The "start at index 0" refers to where the jumping sequence starts, not where your program must start. The program is not the jumping sequence, the program is a feasibility check
where can I find these exercises?
Leetcode...its a website
Or codeforces
Dance at the end
I love dancing
Idk but this code looks weird. And it also possible that it loops endlessly.
I'm not exactly sure though.
Also max jump, doesn't it mean, you can also jump lower than the max jump?
It won't loop endlessly, and it turns out you really only need to consider the max jump
I see.my bad. I thought somehow, the goal or max_jump will affect i
For the second test cases while the same code return true but its actually is false
Not as easy as it looks
🙄
#include
#include
bool can_jump(int *arr, int len)
{
if (!arr || len = len) return false;
}
return false;
}
void print_bool(bool v)
{
if (v) {
printf("True");
return;
}
printf("False");
}
int main()
{
int arr[] = {2, 3, 1, 1, 4};
print_bool(can_jump(arr, 5));
int arr2[] = {3, 2, 1, 0, 4};
print_bool(can_jump(arr2, 5));
return 0;
}
I think I have something similar to yours, but then the python version. It also includes the scenario of example 2 where you end up on the value 0
Seems like your algorithm is not correct. Try array [2,3,0,4]. His algorithm will return true, but, as far as I can see, yours will return false at second step inside while.
@@dontlike1000 Are you sure, because I think both versions will return false?
@@Pevi70 Yes, I've checked author's python code with [2,3,0,4]. It returns true (and it is correct).
@@dontlike1000 Are you sure that is correct, because it will never reach the last index?