Greedy Algorithm - Jump Game - Leetcode 55 

Master Data Structures & Algorithms For FREE at AlgoMap.io!

Thank you RU-vid 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

Ohh yes, the classic if ....: return True else: return False

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 ❤️

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?

Would a greedy algorithm still work if you had to return the shortest path?

Looks DP enough 😅, o(n) is also workable

How's this faster/easier than going forward?

Why not res := len(arr) % arr[0] ; if res != 0 { return false } else { return true } ?

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

Should you not start the iteration from n-2?

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.

Sir,what if the array have [2,2,2,4]?

this guy reminds me of my ex boss.. he used to do insanely complex things where solution was super simple

where can I find these exercises?

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

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?

Dance at the end

I can't understand this someone help please😭

what even?

Dint have time

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