Excellent explanation, you explain the algorithms so easy and well. Observation: You can write the last line of code as: return goal == 0. regards!
@pankajjatav6448 Жыл бұрын
Also you can start loop from second last element: for i in range(len(nums)-2, -1, -1):
@yonavoss-andreae4952 Жыл бұрын
@@pankajjatav6448 that triggers an edge case in which two elements returns false ie [1,2]
@gordonwu81179 ай бұрын
@@yonavoss-andreae4952 if length is 0 then "i" will start on index 0, which works as intended
@brain_station_videos6 ай бұрын
or simply return not goal
@hash00ify2 жыл бұрын
we can start the loop from the len(nums) - 2 position since goal is already set at the last position when we declare it.
@shashanksrivastava7262 Жыл бұрын
I am acturally surprised how his code actually worked like, wouldn't i+nums[i] be always greater than goal ?
@anupamkolay193 Жыл бұрын
@@shashanksrivastava7262 Yes I'm also thinking about that too.
@quanghuyluong1249 Жыл бұрын
@@shashanksrivastava7262 Consider [3,2,1,0,4]: i+nums[i] would not be greater and the goal will never be shifted
@experiment8924 Жыл бұрын
@@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.
@shravankumar371711 ай бұрын
Thats why in this example we cannot reach last element. Algorithm works
@gunishjain93072 жыл бұрын
12:00 jaw dropping intuition, I could have never thought about it. Thanks for the explanation.
@andrepinto78952 жыл бұрын
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;
@ma_sundermeyer Жыл бұрын
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
@PippyPappyPatterson Жыл бұрын
@@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.
@eku333 Жыл бұрын
@@PippyPappyPatterson I disagree. NeetCode's solution is easier to understand imo.
@PippyPappyPatterson Жыл бұрын
@@eku333 do u normally iterate across ur arrays in reverse? or forwards?
@eku333 Жыл бұрын
@@PippyPappyPatterson iterating over an array in reverse is not a rarely used dp technique.
@yankindeez2 жыл бұрын
Thanks!
@kalintoshev2 жыл бұрын
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?
@sivaprakashkkumar96912 жыл бұрын
how it becomes greedy solution please explain it.
@mangalegends2 жыл бұрын
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
@VipulDessaiBadGAMERbaD2 жыл бұрын
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.
@Sim0000n Жыл бұрын
@@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
@jorgemejia1586 Жыл бұрын
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)
@pritampawar64782 жыл бұрын
that explanation for greedy part was just awesome🔥🔥
@aryehakierman6388 Жыл бұрын
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; };
@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.
@tunepa4418 Жыл бұрын
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)
@archiecalder5252 Жыл бұрын
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
@jffrysith4365 Жыл бұрын
@@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...
@kavabanger88 Жыл бұрын
@@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
@856dtrad910 ай бұрын
@@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
@ronitsrivastava377Ай бұрын
This solution is just wild. Easy and efficient. Love it
@anjanobalesh80462 жыл бұрын
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
@mattgolden100 Жыл бұрын
This really helped me conceptualize. Thank you!
@amitdwivedi9951 Жыл бұрын
plz exlain hy nums [i] >= goal - i ?
@anjanobalesh8046 Жыл бұрын
@@amitdwivedi9951 i didn't get your question ??
@gunadeepakpallikonda Жыл бұрын
Mann!!! That's really helpful 👏🏻 🙂
@suhailf50142 жыл бұрын
These are the questions/solutions that make me fall in love with algorithms :) many many thanks @NeetCode
@phlix17 ай бұрын
I love how simple the solution is. I was sketching out a very complex one :D
@adilsaju3 ай бұрын
thats a unique greedy soln.! awesome!
@briangurka80853 жыл бұрын
greedy approach is brilliant. love it
@emilyplanes70823 жыл бұрын
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.💯❤️
@thomaslee36213 жыл бұрын
You and Tech Dose are my go to for leetcodes.
@NeetCode3 жыл бұрын
Yeah, Tech Dose is really good at explaining.
@MrYp-ds7sz3 жыл бұрын
I found neetcode more clear and easy.
@nemesis_rc3 жыл бұрын
@@MrYp-ds7sz neetcode>techdose
@adithyagowda46422 жыл бұрын
@@nemesis_rc neetcode==techdose
@SM-si2ky2 жыл бұрын
I could come up with the DP memorization solution by myself, but got TLE, the greedy solution is optimal but unintuitive.
@freindimania117 ай бұрын
Had the same experience, DP with memo got me TLE, however DP with tabulation got through - although still slower than other submissions.
@gompro3 жыл бұрын
This channel is so much underrated. This video is just amazing!
@heethjain212 жыл бұрын
That greedy solution is ingenius. I am in awe!! Thank you.
@learnwithcode421119 күн бұрын
People often feel frustrated when optimization is prioritized over brute-force solutions. It’s important to start with a simple brute-force approach to fully understand the problem before jumping into optimizations. This foundational step helps clarify the problem and makes it easier to build upon with efficient solutions. Let's focus on presenting clear brute-force solutions first and use general coding constructs to make problem-solving more accessible and translatable.
@pekarna2 жыл бұрын
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.
@Marcelo-yp9uz2 жыл бұрын
I think that's no longer O(n)
@ku-11192 жыл бұрын
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.
@bryanleow50242 жыл бұрын
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]
@jackie03152 жыл бұрын
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?
@guneskedi5 ай бұрын
Oh my god I cannot believe I can finally understand, design the steps and write the correct code! Finally my work paid off!!
@manoelquirino50813 жыл бұрын
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
@RS-vu4nn2 жыл бұрын
He is doing exactly the same thing but more efficiently
@siddhantwaghanna4795 Жыл бұрын
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....
@case6339 Жыл бұрын
Finally someone answered! Appreciated.
@yuzhenwang81039 ай бұрын
Great Explanation! Thx for making it clearer for greedy algorithm
@cwash082 жыл бұрын
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.
@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!
@Andhere-Ki-Aahat2 жыл бұрын
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.
@dinkleberg7943 жыл бұрын
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?
@kneeyaa2 жыл бұрын
I targeted 5 q each day to achieve all in 15 days
@haroldobasi25452 жыл бұрын
@@kneeyaa that’s crazy actually
@AhmadMasud-k9k16 күн бұрын
your last line for the greedy solution can be simplified to return goal == 0 since "goal == 0" itself is a condition
@mmeetp2 жыл бұрын
You can skip the last index check by initiating for loop len(nums) -2
@ancai5498 Жыл бұрын
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
@danmartin1621 Жыл бұрын
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.
@kjplayz30643 ай бұрын
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?
@harshavardhini20823 ай бұрын
bro is a genius for coming up with that greedy solution THANK YOUU FOR THIS VIDEO!
@enesyazici23733 жыл бұрын
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
@robalexnat2 жыл бұрын
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.
@rajeevkri1232 жыл бұрын
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; }
@kaustav073 жыл бұрын
Is it just me or the DP solution giving TLE?
@NeetCode3 жыл бұрын
Yes it gives me TLE too, idk why leetcode does that. For some reason they only accept the greedy solution.
@kaustav073 жыл бұрын
@@NeetCode Thank you.
@nemesis_rc3 жыл бұрын
@@NeetCode can you give dp solution here pls
@josh1234567892 Жыл бұрын
Love when I can implement someone's explanation without directly looking at the implementation. Thank you so much brotha
@NeetCode Жыл бұрын
Nice! 💪
@shihabrashid5837 Жыл бұрын
O(n^2) DP solution gives TLE, thats pretty sad considering the greedy approach may not be apparent to many in an actual interview.
@elias0430114 ай бұрын
Having a hard time understanding why [2, 0, 0] would work with the greedy solution... if you look left of the final 0, would it not be possible to reach the final item?
@Kaviarasu_NS7 ай бұрын
I have started to binge watch Neet ode recently, 2024 is going to be awesome ❤
@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
@user-ul2mw6fu2e5 ай бұрын
class Solution: def canJump(self, nums: List[int]) -> bool: l = len(nums) - 2 r = len(nums) - 1 curr_dist = 0 while l > -1: if nums[l]>= r - l : r-=(r-l) elif nums[l] < r - l and l==0: return False l-=1 return True
@JimmyKal6 ай бұрын
1 minute of silence for those that tried the brute force in an interview
@Dhruvbala2 ай бұрын
If you want to figure out whether a goal is attainable, work backward to figure out what's the easiest first step. You can achieve your goal iff that first step is within reach.
@sampannapokhrel8 ай бұрын
At 9:53, you said the time complexity is O(n ^2).If you use a Memoization Hash or array, it would be O(n).
@marq_89766 ай бұрын
I still don't understand how it works for the FALSE example.
@MrM2JT Жыл бұрын
The greedy approach is simply mind-blowing!
@MsSkip603 жыл бұрын
Get in there, Neetcode!!!! I'm not sure how you feel about it but man, your videos are top notch compared to rest of the leetcode content creators
@gargibiswas86192 жыл бұрын
This is the best greedy solution I have seen till now!
@youssifgamal8545 Жыл бұрын
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
@aninditaghosh6167 Жыл бұрын
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!
@theantonlulz2 жыл бұрын
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".
@Rajmanov7 ай бұрын
Due to its more comprehensive nature, simplicity doesn't always equate to superiority.
@tejaspoojary53973 жыл бұрын
Great explanation!! but wont the for loop start from len(nums)-2 ???
@pritam-kunduu Жыл бұрын
The last statement can be simplified to just goal == 0 Or even further bool(goal)
@АлександрЯрулин-й7и2 жыл бұрын
Thanks. You're very talented in explanation.
@ghzich0172 жыл бұрын
What software do you used to draw? on this scene 9:23
@findingMyself.25yearsago Жыл бұрын
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)
@janaSdjАй бұрын
I solved it by using BFS technique: bool canJump(vector& nums) { int n = nums.size(); queueq; q.push(0); vectorvisited(nums.size(),0); visited[0]=1; while(!q.empty()){ int curInd = q.front(); q.pop(); if(nums[curInd]+curInd>=n-1){ return true; } for(int i=1;i
@brandonicr6913 Жыл бұрын
In the example array [2,3,1,1,4] World but what happen with the greedy solution as you defined when the array is [1,3,1,1,4]?
@ZQutui3 жыл бұрын
Thank you for these videos, I found you recently and you are the channel I have been looking for
@asthapandey9587 Жыл бұрын
It fails for[2,0,0] as we are only checking jump by 1 from previous element of goalpost element.
@awsaf492 жыл бұрын
I'm just wondering what would happen if it was mentioned that we have to choose the shortest path instead of any path? Then I think the Greedy technique might not have been worked...
@gpudoctor Жыл бұрын
Definitely not
@DavidDLee Жыл бұрын
It's not clear why the greedy algorithm is guaranteed to find a solution, if one exists. Is it possible that for some input, with a solution, the greedy algorithm will not find a solution?
@gauravgosain8709 Жыл бұрын
What if n-1 is 0 itself. Would'nt you have to backtrack ex - [2,3,0,1] so i + nums[i] < goal but I can reach there
@Gameplay-ps9ub Жыл бұрын
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. :)
@Aminbenabdelhafidh15 күн бұрын
Great Solution and explanation, but instead of return True if goal == 0 else False you can just put return goal == 0
@SHUBHAMRAGHUWANSHI_ASKN Жыл бұрын
The simpler approach would be: For each reachable index: we update the max reachable index which we can reach. If anytime we reach till end we found the solution. working code: int index = 0, reachable = 0, n = nums.length; while (index = n - 1) { return true; } index++; } return false;
@KCML0362 жыл бұрын
amazing explanation. It really showcase why greedy approach can work wonders sometimes
@Getentertainedp Жыл бұрын
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.
@jugsma66765 ай бұрын
This is the O(n^2) solution, but time exceeds in leetcode : def canJump(nums: list[int]) -> bool: cache = [False] * len(nums) cache[len(nums)-1] = True for i in range(len(nums)-1, -1, -1): for j in range(i+1 + nums[i]): cache[i] = cache[i] or cache[j] return cache[0]
@loliconneko2 жыл бұрын
another solution that come to my mind is building adj list (graph) from the array and then use BFS from index 0 to find path to last index, this should have time complexity O(N) and space complexity O(E) which E is edges in graph, but greedy solution is also awesome since space complexity is O(1) 👍
@findingMyself.25yearsago Жыл бұрын
yes it would be another great approach, can you share the code if you have in handy? would be helpful
@TheChlomek7 ай бұрын
@@findingMyself.25yearsago I wrote this code for this in case it helps anyone in future. It passes 75 of the test cases flagging a 'Memory Limit Exceeded' issue class Solution: def canJump(self, nums: List[int]) -> bool: adj = defaultdict(list) for i in range(len(nums)): for j in range(nums[i]+1): adj[i].append(i+j) q = deque() q.append(0) visited = set() while q: currIndex = q.popleft() if currIndex == len(nums) - 1: return True # we've hit the end if currIndex in visited: continue visited.add(currIndex) for nextIndex in adj[currIndex]: q.append(nextIndex) return False
@dorondavid46982 жыл бұрын
Imagine telling a FAANG interviewer that you're done and the big O is n^n, lol
@meh44663 ай бұрын
My solution is exactly similar to this but a bit more readable : min_req = 1 counter = len(nums)-2 while(counter >= 0): if(nums[counter] >= min_req): counter -= 1 min_req = 1 else: counter -= 1 min_req += 1 if min_req == 1: return True return False
@kjplayz30643 ай бұрын
you can write return (min_req == 1)
@arunanshupadhi2 жыл бұрын
how will the greedy solution work if the input array is [2,3,1,0,4] ? return value should be true as you can jump from 3->4 but you can't shift from 0->4. where will you shift your goal on first iteration?
@loliconneko2 жыл бұрын
you dont need to shift goal on first iterarion if its cant jump to lastest goal (in this case index 4), loop iterator move to 1 and then 3 and now (jump[i] + i >= goalPointer) which is 3 + 1 >= 4, mean we can shift goal pointer to index 1 (value 3) and so on. if the goal pointer reach index 0 then we return true, else return false.
@Osman-ko8jy2 жыл бұрын
Not sure why the Memoization solution doesn't work with Python, but does for JAVA
@abhirup6199 ай бұрын
what if the question has a second part that if yes, then what is the minimum number of jumps? can we do that in linear time?
@SantoshKumar24 ай бұрын
God bless you! 😀 This helped a lot.
@abhinav3325 Жыл бұрын
Thank you so much sir! Your logics and way of explaining is really impressive and make attention to the solution.
@slizverg23 Жыл бұрын
Thanks for the video! Isn't the start of our loop shood be "len(nums)-2" instead of "len(nums)-1"?
@deepakphadatare29492 жыл бұрын
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.
@pabloarkadiuszkalemba74152 жыл бұрын
Why the memoization is O(n^2), if every value is only visited once ?
@apoorvwatsky2 жыл бұрын
Great explanation. No need of ternary tho, returning goal == 0 is enough.
@sonydominates2 жыл бұрын
I went the opposite direction. I started at the beginning and had a pointer that stored the max jumpable value. If the max got stuck and the iterator went above the pointer, it would return false. If the right pointer went to the max index or above, it returns true. Just wanted to explain a different O(N) solution
@arnobchowdhury9641 Жыл бұрын
I did the same. For me that is intuitive. I don't know why the clever solutions always go backwards 😄. I saw the same thing with the Unique Paths problem as well.
@ogundimuhezekiah845 Жыл бұрын
Thanks buddy. You're literally the best
@Divs4311 ай бұрын
May be we should take the range of i from last but one element to compare with goal not upto last element.
@tahirjanjua4106 Жыл бұрын
The for loop should start like this "for i in range(len(nums)-2,-1,-1):"
@mayursonowal Жыл бұрын
How do I know in an interview the DP solution is too slow? I cannot come up with this first time seeing.
@LizzyBartholomew Жыл бұрын
I don't understand why line 5 is range(len(nums), -1, -1, -1). Shouldn't it just be range(len(nums) -1)?
@chanderthakur90055 ай бұрын
i am having a hard time understanding why the condition i + num[i] >= goal works?? can someone please explain , thanks.
@ayushkathpalia89822 жыл бұрын
Hey, i didnt understand the if statement . if i+nums[i]>= goal. why add i to nums[i]. Please explain . Thanks
@29_I2_GirishBhardwaj3 күн бұрын
How do I code up the dp solution
@mister_bake274311 ай бұрын
Thanks mate, helped me a lot. Easy and very quick
@chiragmehta2955 Жыл бұрын
why dp solln is o(n^2) and not o(n) ???
@eliabekun6 ай бұрын
Fantastic! I can't believe that is so simple...Amazing!
@vinobabu73375 ай бұрын
Could someone explain how does Greedy solution work for the tc [10,0,0,0,0,0,0,0,0]