Jump Game - Greedy - Leetcode 55
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/jump-game
0:00 - Read the problem
2:50 - Brute Force Explanation
10:10 - Greedy Explanation
14:05 - Coding Explanation
leetcode 55
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#greedy #array #python - Věda a technologie
Excellent explanation, you explain the algorithms so easy and well. Observation: You can write the last line of code as: return goal == 0. regards!
Also you can start loop from second last element: for i in range(len(nums)-2, -1, -1):
@@pankajjatav6448 that triggers an edge case in which two elements returns false ie [1,2]
@@yonavoss-andreae4952 if length is 0 then "i" will start on index 0, which works as intended
or simply return not goal
12:00 jaw dropping intuition, I could have never thought about it. Thanks for the explanation.
we can start the loop from the len(nums) - 2 position since goal is already set at the last position when we declare it.
I am acturally surprised how his code actually worked like, wouldn't i+nums[i] be always greater than goal ?
@@shashanksrivastava7262 Yes I'm also thinking about that too.
@@shashanksrivastava7262 Consider [3,2,1,0,4]: i+nums[i] would not be greater and the goal will never be shifted
@@shashanksrivastava7262 Yes, i+nums[i] would be greater than goal for the first iteration, which would satisfy the if statement but the goal will be the same, i.e the last index and the program would move on the next iteration and work as usual.
Thats why in this example we cannot reach last element. Algorithm works
that explanation for greedy part was just awesome🔥🔥
Man excellent job. I went through many videos but wasn't able to understand. U made us all feel that it is very simple. Thanks a-lot again.
Thank you for these videos, I found you recently and you are the channel I have been looking for
This channel is so much underrated. This video is just amazing!
That greedy solution is ingenius. I am in awe!!
Thank you.
These are the questions/solutions that make me fall in love with algorithms :)
many many thanks @NeetCode
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 = nums.length-1;
yeah, also started from the beginning, it's more intuitive. You can also stop early at zeros that you can't cross:
max_index = -1
for i in range(len(nums)-1):
if nums[i] == 0 and max_index
@@ma_sundermeyer Why does everyone start from the end? Does it help with other problems that use a similar solution (that can't be implemented front-forwards)? From the beginning is a million times easier to remember.
@@PippyPappyPatterson I disagree. NeetCode's solution is easier to understand imo.
@@eku333 do u normally iterate across ur arrays in reverse? or forwards?
@@PippyPappyPatterson iterating over an array in reverse is not a rarely used dp technique.
amazing explanation. It really showcase why greedy approach can work wonders sometimes
greedy approach is brilliant. love it
Great Explanation! Thx for making it clearer for greedy algorithm
Outstanding illustration with the diagrams. I just tried out the same code looping i from len(nums) - 2 to -1 because anyway the first run didn't alter the goal's position and it got accepted :) thank you so much!
Nice. I practiced the dp solution and got stuck on greedy. I was able to make the connection to the last and second before last elements , but couldn’t think of moving the goalpost as you say. Nice solution.
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?
how it becomes greedy solution please explain it.
This is what I have a little trouble wrapping my brain around. We always pick the first option, but what if the first option is 0? Then we're stuck lol. I guess you could add extra logic to handle that but the greedy solution doesn't seem to have include that
but this prob is not to find optimal path but to find only if we can reach the destination, that is why its okay to select the first elment.
@@mangalegends Let's consider the array 3105. Goal is 3, i is 3. I becomes 2, goal stays the same (as it is 0.) I becomes 1, Goal stays the same as 1+1 is not greater or equal than 3. i becomes 0, but as 0+3 ≥ 3, we're good. So no reason to be stucked
Even if you hit a 0 during the loop, that’s fine. The goal post will be left at an actual reachable/moveable location (aka an index where the value is not zero)
Your explanation works like magic! Thank you so much 😊
Oh my god I cannot believe I can finally understand, design the steps and write the correct code! Finally my work paid off!!
thats an awesome solution and explination!!
I thought of an answer where we only stop our iteration once we come upon a zero. then we just check if we can if the zero can be jumped over by previous elements. the only problem is the edge case where nums= [0],where you got check for it.
var jump = function (nums) {
if (nums.length === 1) return true;
let prevPosition, prevValue;
let passFlag = true;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === 0) {
passFlag = false;
prevPosition = i - 1;
while (prevPosition >= 0) {
prevValue = nums[prevPosition];
if (prevPosition + prevValue > i) {
passFlag = true;
break;
}
prevPosition--;
}
if (!passFlag) return false;
}
}
return true;
};
Love when I can implement someone's explanation without directly looking at the implementation.
Thank you so much brotha
Nice! 💪
Thank you so much sir! Your logics and way of explaining is really impressive and make attention to the solution.
bro is a genius for coming up with that greedy solution THANK YOUU FOR THIS VIDEO!
I love how simple the solution is. I was sketching out a very complex one :D
The greedy approach is simply mind-blowing!
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.
that makes sense but this is still technically O(n^2) right?. consider this example [2,3,4,5,6,7,8,8,0,0,0,0,0,0,0,0,0,0,9]. For every non zero element, we have to do ~n/2 work to check if it crosses over all the zeros (i.e constant amount of work for every non zero element)
Working backwards, if we record the index of the first encountered 0, then the work required to check if an element crosses is constant. @@tunepa4418
@@tunepa4418 no, I think it would be the same way, except we just only start checking once we find a zero. I don't think it'd be any faster though... because you'd still have to check if each value is a zero...
@@tunepa4418if we are going from the end of list and found a zero, and then found a long enough jump to jump over it, we dont care about zeroes between first zero and jump position
@@tunepa4418 O(n)
class Solution:
def canJump(self, nums: List[int]) -> bool:
obstacle = -1
for pos in range(len(nums) - 2, -1, -1):
if nums[pos] == 0 and obstacle == -1:
obstacle = pos
if pos + nums[pos] > obstacle:
obstacle = -1
return obstacle == -1
I think u can also solve it in O(nlogn) using a BIT or segment tree , where u will start from the end and see whether the current node range (l = i , r = i+nums[i]) summation is greater than 0 or r >= nums.size() , if so then update the current node to be one and continue
This is the best greedy solution I have seen till now!
Thanks mate, helped me a lot. Easy and very quick
Thanks. You're very talented in explanation.
The if condition can be modified to
If nums [i] >= goal - i
i.e if the value at the current index is greater than or equal to the difference between the goal and the index
For better understanding 😄 thank you
This really helped me conceptualize. Thank you!
plz exlain hy nums [i] >= goal - i ?
@@amitdwivedi9951 i didn't get your question ??
Mann!!! That's really helpful 👏🏻 🙂
Starting at the end, we always have to traverse the entire length of the array. Starting at the beginning is more performant as we can return true as soon as the current value is > last index - n.
your explanations are really easy to understand. I always look for your videos. I was looking for buy and sell stocks III and IV videos from your channel but did'nt find them. Watched other channel videos but they were not as easy to understand.
really nicely explained man! thank you so much
Awesome solution man! Loved it
excellent video. I am learning a lot from your videos. Great work
You and Tech Dose are my go to for leetcodes.
Yeah, Tech Dose is really good at explaining.
I found neetcode more clear and easy.
@@MrYp-ds7sz neetcode>techdose
@@rajdeepchakraborty7961 neetcode==techdose
Explanation 💯 clean !
Alternative:
1) Start on the right
2) Go to the left, skip all non-zeros
3) On each zero, find any position on the left that can skip it - i.e. larger than the distance from it
4) If there's none, return false
5) If there's any, continue from there, to the point 2)
6) Return true when reaching the left end.
I think that's no longer O(n)
Never stop making these please lol
Thanks buddy. You're literally the best
thats a unique greedy soln.! awesome!
thank you for clearly explanation this question!!!
awesome solution and explanation, thank you !
You can skip the last index check by initiating for loop len(nums) -2
Thanks for your explanation!!
I have started to binge watch Neet ode recently, 2024 is going to be awesome ❤
Really good video, I was stuck trying to do it in a DP way, but this is really clean!
Also, the last line can be simplified to "return goal == 0" as this returns a boolean.
this is the dp solution in O(n^2), but only passes 77/170 on LC due to TLE. I think they really want you to use the greedy approach
class Solution(object):
def canJump(self, nums):
dp = [0 for _ in range(len(nums))]
# goal can be reached from itself
dp[-1] = 1
for i in range(len(nums)-2, -1, -1):
for j in range(1, nums[i]+1):
# as long as one of your descendants (who u can reach from your current spot) can reach the goal, you can too
if (dp[i+j] == 1):
dp[i] = 1
# for better efficiency
break;
return dp[0]
Excellent explanation and great video! Thank you!
Glad it was helpful!
Please keep posting.
Also I have a recommendation. Please add python in your title and thumbnail. You will surely reach more people.
Ex. Jump game leetcode python solution #55 - Greedy approach explained
Thank you for making these videos.💯❤️
nice video! loved the explanation
Amazing explanation!
Fantastic approach love you needcode
God bless you! 😀
This helped a lot.
Absolutely amazing!!!!
What software do you used to draw? on this scene 9:23
One small nitpick in the implementation would be, that you could just return goal==0 (which evaluates to boolean value). Some could say using the ternary / if...else is more readable, but it's a matter of opinion I guess. Nevertheless, great video as always. I truly appreciate the way you explain algo, it's very clear imo. :)
Fantastic! I can't believe that is so simple...Amazing!
I could come up with the DP memorization solution by myself, but got TLE, the greedy solution is optimal but unintuitive.
Had the same experience, DP with memo got me TLE, however DP with tabulation got through - although still slower than other submissions.
Amazing! Thank you so much!
I had a different solution that worked as well. We only can't jump to the end if the array have an element 0 in it and this element isn't the last one. So I loop through every element and check if it was 0, if so, I loop backwards to check if there is an element that can jump over the zero, if so, I'll continue the loop, if not, I'll break and return false
He is doing exactly the same thing but more efficiently
hi if it you could only jump a fixed length (e.g. if the number was 2, and you could only jump 2 spaces, not 1), could you still start from the end? Or must yoi use DP?
Amazing. You made this incredible video explaining the problem and you end it with "return True if goal == 0 else False" instead of just "return goal == 0".
Due to its more comprehensive nature, simplicity doesn't always equate to superiority.
superb video, thanks a ton
youre so good! thank you so much
brilliant solution!
For those who have the question of why is always first element chosen as the next goal in greedy approach:
There are mainly two types of questions you might be facing:
1. Why always chose the first element as next goal post
2. What if I don't get a further route afterwards by choosing the first element. What if I would have chosen other element that time and I would have gotten answer ( In this case you must have thought what if I couldn't have reached 1 in any way, I would have missed the potential answer of keeping 3 as the next goal.....)
Answer:
According to the solution, we chose 1 as our goalpost. In the back of our mind we know it can also be reached by 3. you think that I might get stuck on further exploring the path with 1.
** Take a closer look, my friend, if you can reach 4 from 3, you will also definitely reach 1 from 3 ( because 4 is farther away from 1). So while choosing the first element you have the surety that if there is any other potential answer beyond that index, that index could also be reached with that potential answer(in this case 1 could also be reached by 3 as 4 was reachable by 3). And thus you know that you will get the answer by choosing the first element. **
Hope this clears your doubt....
Finally someone answered! Appreciated.
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
Thank you for the video.
Best explanation ever!
Very good explaination , thanx
Brilliant and elegant!
You are awesome man
Thank you so much!
For anyone who is interested in the dp solution ( C++ version).
bool dfsJump(vector& nums, int i, vector& 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
O(n^2) DP solution gives TLE, thats pretty sad considering the greedy approach may not be apparent to many in an actual interview.
Superb explanation
Thank you!!
for the greedy explanation, what gives us the right to shift the goal post to the FIRST item that can reach it? There can be multiple items that can reach the goal post that are more "left"? ie in [1,3,2,1,5] we shift the goal from 5 to 1 immediately upon encountering 1, instead of looking further to the left such as 2....why is this greediness guaranteed to produce the correct result?
Thanks!
youre amazing keep it up
You made problem soo easy Sir!!!
I love you Mr. NeetCode.
great video
Holy Moly , what a piece of cake.
You are the best!
Nice one🎉
Great videos, can you also explain how you get the time complexities? I am not how sure how you got the n^n and n^2
n^n happens because as for each index number explored, he recursively explores the indices reachable by it, however because he isn't caching it essentially we end up with a lot of repeated work like he mentions. A more visual way of thinking about it: [3,2,1,0,4]. I start with the 3 at index 0, and recursively call (which is the same as a Depth First Search stack implementation) each of the indices reachable (0+1,0+2,0+3) = (1,2,3), I start with index 1. It has a value of 2, same as before, I then have another recursive call to index 2 with value 1, until we reach 0. Now when the stack unfolds, BECAUSE we did not cache, we still end up calling all the branches as before. Meaning when we roll back to index 1 (the one that had value 2), we only explored the first of (1+1,1+2) aka index 2, but we didn't make a call yet for index 3. With Caching this is reduced significantly, and essentially becomes a n + (n-1) + (n-2) +...+1 complexity problem which, when we drop lower terms, we get as O(n^2). Hope this is more clear.
amazing content
loved the soln.!!
Amazing!
Great explanation!! but wont the for loop start from len(nums)-2 ???
Java code the same
public boolean canJump1(int[] nums) {
int goal = nums.length - 1;
for(int i = nums.length - 1; i>= 0; i--) {
if(i + nums[i] >= goal) {
goal = i;
}
}
return goal == 0;
}
Forward approach
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
max_goal_reached = 0
for index in range(n):
if index > max_goal_reached:
return False
new_goal = nums[index] + index
if new_goal > max_goal_reached:
max_goal_reached = new_goal
if max_goal_reached >= n - 1:
return True
return False
Just adding my DP solution for understanding the approach, but anyhow as he said in video because of n^2 it will give TLE
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
dp = set()
def dfs(index):
if index in dp:
return False
if index >= n - 1:
return True
for next_index in reversed(range(index + 1, nums[index] + index + 1)):
if next_index in range(n):
result = dfs(next_index)
dp.add(next_index)
if result:
return True
return False
return dfs(0)
Very good video
i never comment but this explanation made my jaw drop
Just fabulous 🤩🤩
Hey Neetcode, do you have any videos on your routine when your were leetgrinding? Like how many questions per day u were doing and how long it took u to complete the 75 questions list?
I targeted 5 q each day to achieve all in 15 days
@@kneeyaa that’s crazy actually
Can you show how to code the DP solution?
Because I can draw the tree but I can't code the solution.I get stuck at this step.
Not sure why the Memoization solution doesn't work with Python, but does for JAVA
you are a boss !!