Thank you very much. I started my day working on this question and I spent an hour and did not understand anything from various solutions that I looked into. I was frustrated and suddenly I found your video. I completely got it now, I am really thankful to you.
This is O(n^2). An easier to understand O(n^2) solution would be to traverse the array backwards and keep filling in values. Define new array as arr[n]. arr[last] will be 0. If we are at position i and input[i] = 5 we need to check the next 5 values in our arr and put arr[i] = min(all those values). Do this 1 by 1 backwards. Return arr[0].
@@sachinchandwani4085 Can you please elaborate on what you are trying to say. Actually, I also thought of the solution mentioned by. I would love to know the cases where that could fail.
MANSI AGARWAL I’ve tried this logic. if array is of all 1’s then you’d get TLE. And about my comment- i was saying that if solution contains jump where you don’t have to make jump of maximum length then you’d have to try all possible jumps which will take more time too
@@mansiagarwal3677 class Solution: def jump(self, nums: List[int]) -> int: if len(nums) ==1: return 0 dp = [0 for _ in range(len(nums))] for i in range(len(nums)-2,-1,-1): temp = float("inf") for j in range(1,nums[i]+1): if i+j < len(nums): temp = min(temp, dp[i+j] ) dp[i] = temp+1 return dp[0]
DP is nothing but careful bruteforce so we are simply trying all possibilities but carefully keep this in mind and build recursion tree and store subproblems
Forget everything, solve it with brute force , observe the pattern , if code is getting executed multiple times with same variables , that means you somehow need to avoid that extra executions , and that's where you think of optimizing the solution. DP is not the only solution, it helps in optimization.
Lovely explanation Tushar! In fact, you don't need the second array; it's possible to reconstruct the jumps you took simply from the jump array. For example, let `i` = 9 (the last index of our array). At `jumps[9]` we have a value of 4. You know then that you must have got here from an index with a jump number of 3. So you can send another pointer `j` back through `arr` and `jumps` until you find an index such that `jumps[j]` equals 3 and `arr[j]` is sufficiently large to reach index `i`. When you have such an index `i` you can safetly conclude that this is one of your jumps, so add it to your output. Repeat the process until you eventually reach index 0.
The greedy solution works here, yielding a O(n) time / O(1) space : when you're at index i, you just optimize the next jump by taking the index max (i < j
I guess we can optimize this a little bit by analyzing the actual jump array.. instead of starting i from 0, we can check the actual jump array of previous element and start i from that index. for e:g in your array at 5th index, the value is 4, here we can check the previous element i.e 2 which is at index 4 and its actual jump index, if that value required 2 jumps then there is no way that the index 5 can be reached from index 0 directly.So, instead we can start i from the previous element's actual jump array.
for 1st example you are jumping to next element which is from 2 to 3 and from 2 to 4 (1 element jump). Same for 3 your jumping 3 elements !!! why for 2 only 1 element jump ??
It is not mandatory to make the maximum possible jumps from one point. The requirement is to keep the total jumps minimum. So, if u make 2 jumps from there u r landing in 2 and subsequently u make another 2 jumps to land in 1 and then another jump to reach the final point. Finally, it would results in 5 jumps in total instead of 4 which is the minimum one.
If a problem has optimal substructure and overlapping subproblems, then either DP or Greedy solution may apply. This is explain in detail in the CLRS book.
We can use graph over here make a connection of indexes will be based on jump given and then we can use dfs bfs anything and check whether we have visited that node or not during traversal .
simpler solution: l=[2,4,1,7] jumps=0 end=0 farthest=0 for i in range(len(l)-1): farthest=max(farthest,i+l[i]) if(i==end): jumps+=1 end=farthest print(jumps)
i am very thankful 2 you...i was struggling to learn DP but now i will able to understand and solve dp question from your video...if possible provide similar questions on codechef or hacker eerth...and keep making lots of vids
Why DP is required here?, Just we have to pick max jump value with in the given possibilities e.g) on given array 3,4,3,3,... the possibilities are 4,3,3 and we have to choose the second 3 which will give us the next maximum possibilities rit?
I just wanted to know what is the logic behind moving of i and j ? In , other words you should explain when are we actually backtracking j and when we are incrementing i . You blindly explained the dry run of the algorithm instead of explaining the intuition which led to the formation of the algorithm.
Hey Tushar, Can the above Qn be solved with this algorithm? Step 1: We've an array of the same size as the no of elements in the array signifying no of jumps it takes to reach the last element. Hence, we initialize it with infinity initially and mark the last cell as 0 since the last element can reach itself with 1 jump. Step 2: We see what all elements can reach the last element with 1 jump, then update those element's cell as #jumps to reach the last element (which will be zero initially by step 1). Step 3: We see if the first element is reachable with a value less than infinity. If yes terminate else we mark the nearest element to the first element as the last element and goto step 2. Tell me if there's anything wrong with this algorithm. Thanks.
Sir , Can you explain one thing,If we add a constraint in the question that is we need to visit every point exactly once and then ,if we ask In how many ways you can reach at the end ,than what will be the answer
what if the value at index 0 was 0 then it wouldnt have been possible to reach the end.Likewise there are lots of possibilities when we cant get any solution. Could you add that part too
In the no of jumps array at index 3, while calulating min no. of jumps to reach 3 from 1, won't the number of jumps required be 3, since min no. of jumps to reach 1 + min no. of jums req from 1 to 3 i.e(1+2)?
Is there a way to trace your steps using only the solution array? I know you can with some DP problems. Was wondering if this is possible for this problem.
Can you please give a solution to dis {1,0,5,8,0,0,6,0,0,8,9} The answer should be -1 since we cannot reach the end. But how to achieve it using the program you gave. I'm getting the value of MAX_INT... how to edit it according to this case. Thanks in advance.
Simple, do a recursive search. Keep track of the fewest numbers of jumps found so far. Don't search if more from that point is the number of jumps exceeds the fewest so far.
Nice solution, but can be solved in a lot more simpler way class Solution { public int jump(int[] nums) { if(nums.length == 1) return 0; int res = 0; int currJump =0; int currJumpCopy = currJump; for(int i = 0; i< nums.length-1; i++){ currJump = Math.max(currJump, nums[i]+i); if(i == currJumpCopy){ res++; currJumpCopy = currJump; } } return res; } }
See Friendly Developer channel DP Deep Dive series . He explains each problem with all the required intuition and reasons that is very easy to understand.
I solved this question on leetcode with same lagic but it got TLE for only 2 test cases out of 95, I thought you will tell about any better approach can you??
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
Captions Autogenerator: My name is too sharp😂😂
ruclips.net/p/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3
I guess he is too sharp :p
Thank you very much. I started my day working on this question and I spent an hour and did not understand anything from various solutions that I looked into. I was frustrated and suddenly I found your video. I completely got it now, I am really thankful to you.
This is O(n^2). An easier to understand O(n^2) solution would be to traverse the array backwards and keep filling in values. Define new array as arr[n]. arr[last] will be 0. If we are at position i and input[i] = 5 we need to check the next 5 values in our arr and put arr[i] = min(all those values). Do this 1 by 1 backwards. Return arr[0].
Soumyajit Ganguly yes this is the more intuitive solution too.
I thought that too. But problem comes in the solutions where you didn't have to make maximum length jump. Hence it got TLE in this solution.
@@sachinchandwani4085 Can you please elaborate on what you are trying to say. Actually, I also thought of the solution mentioned by. I would love to know the cases where that could fail.
MANSI AGARWAL I’ve tried this logic. if array is of all 1’s then you’d get TLE. And about my comment- i was saying that if solution contains jump where you don’t have to make jump of maximum length then you’d have to try all possible jumps which will take more time too
@@mansiagarwal3677
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) ==1: return 0
dp = [0 for _ in range(len(nums))]
for i in range(len(nums)-2,-1,-1):
temp = float("inf")
for j in range(1,nums[i]+1):
if i+j < len(nums):
temp = min(temp, dp[i+j] )
dp[i] = temp+1
return dp[0]
I just want to know how do you get intuition of these dp approaches.
when my solution gives TLE then I get an intuition of DP approach.
Exactly 😭
Basically think step by step. Like for this problem. Think as for array len 1 ,then for 2 .. so on
DP is nothing but careful bruteforce so we are simply trying all possibilities but carefully keep this in mind and build recursion tree and store subproblems
Forget everything, solve it with brute force , observe the pattern , if code is getting executed multiple times with same variables , that means you somehow need to avoid that extra executions , and that's where you think of optimizing the solution.
DP is not the only solution, it helps in optimization.
Tushar Roy: "yes..we will use dp to solve this problem"
Me: But why??
Exactly my point brother. Moreover O(n^2) solutions aren't even accepted.
Excellent explanation . absolutely loved the blackboard style teaching.
Lovely explanation Tushar!
In fact, you don't need the second array; it's possible to reconstruct the jumps you took simply from the jump array.
For example, let `i` = 9 (the last index of our array). At `jumps[9]` we have a value of 4. You know then that you must have got here from an index with a jump number of 3. So you can send another pointer `j` back through `arr` and `jumps` until you find an index such that `jumps[j]` equals 3 and `arr[j]` is sufficiently large to reach index `i`. When you have such an index `i` you can safetly conclude that this is one of your jumps, so add it to your output.
Repeat the process until you eventually reach index 0.
The greedy solution works here, yielding a O(n) time / O(1) space : when you're at index i, you just optimize the next jump by taking the index max (i < j
can u share the code pls!
@@brainfreeze192 github.com/Errichto/youtube/blob/master/leetcode/april-2020-challenge/25-jump-game.cpp
I guess we can optimize this a little bit by analyzing the actual jump array.. instead of starting i from 0, we can check the actual jump array of previous element and start i from that index. for e:g in your array at 5th index, the value is 4, here we can check the previous element i.e 2 which is at index 4 and its actual jump index, if that value required 2 jumps then there is no way that the index 5 can be reached from index 0 directly.So, instead we can start i from the previous element's actual jump array.
for 1st example you are jumping to next element which is from 2 to 3 and from 2 to 4 (1 element jump). Same for 3 your jumping 3 elements !!! why for 2 only 1 element jump ??
It is not mandatory to make the maximum possible jumps from one point. The requirement is to keep the total jumps minimum. So, if u make 2 jumps from there u r landing in 2 and subsequently u make another 2 jumps to land in 1 and then another jump to reach the final point. Finally, it would results in 5 jumps in total instead of 4 which is the minimum one.
@@anilantony2068 Thats why I thought everyone is wrong!, GOT it. :v
Hey Tushar, you are doing a great job!! just a thought. Can you please explain how to decide, if a problem can be solved with DP approach. Thanks.
If a problem has optimal substructure and overlapping subproblems, then either DP or Greedy solution may apply. This is explain in detail in the CLRS book.
this guy just follows his algo without telling us why he formulated that algorithm
@@sureshchaudhari4465 Just put some efforts of your own too.
We can use graph over here make a connection of indexes will be based on jump given and then we can use dfs bfs anything and check whether we have visited that node or not during traversal .
Tushar: "Yes, we'll use Dynamic Programming to solve this problem"
Me(Beginner): "Why the fuck he is choosing DP? Care to elaborate?" :|
Could you explain the O(n) approach as well? thank you
Awesome sir! I have viewed a couple of your lectures on dynamic programming and i find the explanation really nice and to the point . Thanks a lot! :)
simpler solution:
l=[2,4,1,7]
jumps=0
end=0
farthest=0
for i in range(len(l)-1):
farthest=max(farthest,i+l[i])
if(i==end):
jumps+=1
end=farthest
print(jumps)
Can we use Bfs for this like in Snake and ladder problem to find min steps to reach the Goal?
yes u can
And how would one do that?
I kindof understood nothing ...
i am very thankful 2 you...i was struggling to learn DP but now i will able to understand and solve dp question from your video...if possible provide similar questions on codechef or hacker eerth...and keep making lots of vids
bhai tu GOD hai Massive Respect
everything is temporary but watching video of tushar Roy after stuck in DP problem is permanent.(100th comment is mine)
ruclips.net/p/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3
- problem desciption -
So how do we solve this?
yes, we will use dynamic programming to solve this
do we always need to set the j back to 0? wouldn't it be enough to set j to the last number in the actual jump array?
Why DP is required here?, Just we have to pick max jump value with in the given possibilities e.g) on given array 3,4,3,3,... the possibilities are 4,3,3 and we have to choose the second 3 which will give us the next maximum possibilities rit?
second 3 because MAX(4 - 2, 3 - 1, 3 - 0) which second three.
I just wanted to know what is the logic behind moving of i and j ? In , other words you should explain when are we actually backtracking j and when we are incrementing i . You blindly explained the dry run of the algorithm instead of explaining the intuition which led to the formation of the algorithm.
great video:) the way u depict how the matrix or array gets filled solves everything for me.. writing the code becomes cakewalk thnks :)
You always makes dp easy for us
Hey Tushar,
Can the above Qn be solved with this algorithm?
Step 1: We've an array of the same size as the no of elements in the array signifying no of jumps it takes to reach the last element. Hence, we initialize it with infinity initially and mark the last cell as 0 since the last element can reach itself with 1 jump.
Step 2: We see what all elements can reach the last element with 1 jump, then update those element's cell as #jumps to reach the last element (which will be zero initially by step 1).
Step 3: We see if the first element is reachable with a value less than infinity. If yes terminate else we mark the nearest element to the first element as the last element and goto step 2.
Tell me if there's anything wrong with this algorithm. Thanks.
Sir , Can you explain one thing,If we add a constraint in the question that is we need to visit every point exactly once and then ,if we ask In how many ways you can reach at the end ,than what will be the answer
In the code sample on github, shouldn't "for(int j=0; j < arr.length; j++){" have the middle condition of "j < i" ?
Thanks for your video, great stuff
Awesome explaination!!! Keep up the great work buddy
Hello Tushar, At index 4 value is 2 so it should be two jumps and not 4 jumps right ?
what if the value at index 0 was 0 then it wouldnt have been possible to reach the end.Likewise there are lots of possibilities when we cant get any solution. Could you add that part too
Nice Video Tushar !!! Thanks a lot for taking time and sharing your knowledge.
In the no of jumps array at index 3, while calulating min no. of jumps to reach 3 from 1, won't the number of jumps required be 3, since min no. of jumps to reach 1 + min no. of jums req from 1 to 3 i.e(1+2)?
you should have told naive approach for all the questions before the dp approach
yes we will use dynamic programming to aolve this qn.
EPIC
Best solution is in O(N).
can't we find the max of the elements of subarray which we can jump and jump to that position
Is there a way to trace your steps using only the solution array? I know you can with some DP problems. Was wondering if this is possible for this problem.
Very well explanation sir🙏
What if we have -ve number ?
Great video.Need more on dynamic programming with some code descriptions.
I am thoroughly enjoying your explanations.. Thanks a lot.. Great work.. Spell correction: Mimimum -> Minimum
I think we can also use BFS to find min jumps.
Yes, that would be the best approach to solve this problem.
Can you please give a solution to dis {1,0,5,8,0,0,6,0,0,8,9}
The answer should be -1 since we cannot reach the end. But how to achieve it using the program you gave. I'm getting the value of MAX_INT... how to edit it according to this case.
Thanks in advance.
Simple, do a recursive search. Keep track of the fewest numbers of jumps found so far. Don't search if more from that point is the number of jumps exceeds the fewest so far.
Nice solution, but can be solved in a lot more simpler way
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int res = 0; int currJump =0; int currJumpCopy = currJump;
for(int i = 0; i< nums.length-1; i++){
currJump = Math.max(currJump, nums[i]+i);
if(i == currJumpCopy){
res++;
currJumpCopy = currJump;
}
}
return res;
}
}
Tushar is the God of Dynammic Programming.
Much more easier solution:
public int jump(int[] A) {
int max=0;
int e=0;
int sc=0;
for( int i=0;i
You could have used Greedy Algorithm too! That would be a more efficient solution!
greedy will give wrong solution.
Hello Tushar I can't understand ur egg dropping problem....
good solution using dp , thanks for the video
How u came to know that this problem is D.P problem..??
As always, love Tushar's (the master dynamic programmer!) videos.
There is a linear solution to this problem which uses a greedy approach
I dont get the table to equation portion. Can anyone help me?
What if there are negative numbers in the array?
Bruh 😂😂
😂
See Friendly Developer channel DP Deep Dive series . He explains each problem with all the required intuition and reasons that is very easy to understand.
ruclips.net/p/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3
sir could you keep the solution to this program using graph approach
Can you please solve this problem as well.
From leetcode: Odd Even Jump
You need more explanation man on why to use DP n all.
sir you are the best
nice explanation
why is this so complex ???
🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
waiting for ur new video ...
@Tushar, This can be done in O(n).
Here is the solution: github.com/AnkitChaudhary2601/ds/commit/6a9491768c848117ead70bcdc7c8b184c8009765
Your without dp solution gives different result for the test case. n=6 arr= {3,3,4,1,5,2}. You should check this.
Can you please upload o(n) solution
This method will yeild TLE . best approach is Greedy Ladder approach.
isko kuch aata bhe h? Raat ke aaya hua lagta h ye
Could be done in O(n), slow solution
can we solve it in O(n)??
yes...you can do that with greedy algo approach
'Yes we will use dynamic programming" 😎😎😎
Dude.. I guess this method isn't optimized.
good approach but its showing as Time Limit Exceed
Same here, by this explanation, on leed code showing Time Limit Exceed
Thank You
This problem can be solved in O(n)..
hholy shit. how?
nothing clear
my brain hurts
fantastic. tahnks
U can solve it in o(n)
ruclips.net/p/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3
thanks Tushar. this can done cleanly using 2D matrix.
How?
Thank you Tushar
Need O(n) Solution..!!
I solved this question on leetcode with same lagic but it got TLE for only 2 test cases out of 95, I thought you will tell about any better approach can you??
There is O(n) solution for this problem - BFS
very helpful
***** This can be solved by greedy approach also.....
U the best
Whiteboard expl very useful
ruclips.net/p/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3
difficult to understand , too fast, he didnt explain how did he get array values 2, 3 1 1 ,,,,,,and also he uses 2 extra spaces (arays)
Can check this video if it helps ruclips.net/video/WyIDphqyUCU/видео.html
THis approach gives TLE
sala ratta marke aaya hai
bade aaram se
O(n) !!!!!!!!!!
What?
Ur English so irritate aap engrejo vali English kyo bolre ho kya jaareurat hh iski normal bi to bol skte go
the guy doesn't has teaching acumen. poor video. wish Aditya would have made this video
Noob solution!! .. Give us the O(n) solution
Bhhhhhhh