@hash00ify
we can start the loop from the len(nums) - 2 position since goal is already set at the last position when we declare it.
@gunishjain9307
12:00 jaw dropping intuition, I could have never thought about it. Thanks for the explanation.
@yankindeez
Thanks!
@kalintoshev
The tricky part of the greedy is to prove that it actually works; we clearly have multiple options for moving the goal and we always pick the first one. How do we guarantee that we are not going to get stuck using this approach?
@sentinel-y8l
There is no need to start from the end and move backwards. You can naturally progress from the beginning, like this:
int reach = 0;
for (int i = 0; i < nums.length && i <= reach; i++)
reach = Math.max(reach, i+nums[i]);
return reach >= nums.length-1;
@pritampawar6478
that explanation for greedy part was just awesome🔥🔥
@briangurka8085
greedy approach is brilliant. love it
@sdgslkdjhglsdh
Funnily enough I did the opposite of your sliding the goal approach by keeping track of your maximum remaining jump at current position. This allows early returning with a fail code instead of having to parse the whole array.
in c#:
public bool CanJump(int[] nums)
{
int j = 1;
for (int i = 0; i < nums.Length - 1; i++)
{
j--;
if (nums[i] > j)
j = nums[i];
if (j == 0)
return false;
}
return true;
}
@gompro
This channel is so much underrated. This video is just amazing!
@ancai5498
For anyone who is interested in the dp solution ( C++ version).
bool dfsJump(vector<int>& nums, int i, vector<int>& cache) {
if (i >= nums.size() - 1) { // reaches or beyond last element
return true;
}
if (cache[i] != -1) {
return cache[i];
}
// starts from i, maximum can jump
for (int j = 1; j <= nums[i]; j++) {
if (dfsJump(nums, i + j, cache)) {
return true;
}
}
cache[i] = false;
return false;
}
bool canJump(vector<int>& nums) {
vector<int> dp(nums.size(), -1);
return dfsJump(nums, 0, dp);
}
@thomaslee3621
You and Tech Dose are my go to for leetcodes.
@suhailf5014
These are the questions/solutions that make me fall in love with algorithms :) many many thanks @NeetCode
@baetz2
You can also solve this problem by finding zeroes in the array and check if there are numbers before zeroes long enough to jump over zero. For example, if you see [3,2,1,0,...], you can instantly tell you're stuck at 0.
@PabitraPadhy
Glad I watched the visual for the idea behind the greedy sol. My first idea was to use the BFS, with a visited array. then I optimized to use the input array as visited, but the runtime and memory was high among other submissions in leetcode. Then I found the greedy solution, and I wanted to know why and how of it. This video explains it.
@heethjain21
That greedy solution is ingenius. I am in awe!! Thank you.
@ronitsrivastava377
This solution is just wild. Easy and efficient. Love it
@yuzhenwang8103
Great Explanation! Thx for making it clearer for greedy algorithm
@kenhaley4
Optimization: Notice that you can always jump forward unless you run into a zero. Therefore, just check each zero (if any), and make sure there's a number to the left that's big enough to jump over it. It's a little more code, but much faster, especially if the array is huge but only has a few zeros. Here's my solution:
start = 0
while True:
try:
pos = nums.index(0, start, len(nums) - 1)
except ValueError: # no more zeros found
break
for ptr in range(pos - 1, -1, -1):
if nums[ptr] > pos - ptr:
break
else:
return False
start = pos + 1
return True
@sscapture
Spent couple of hours with this task :( after watching first 3 minutes of the video, was able to write the solution. You're God!
@davidbanda4727