Minimum jump to reach end
Vložit
- čas přidán 27. 03. 2015
- Given an array, find minimum number to jumps to reach end of array, given you can jump at max as much as value at position in array.
github.com/mission-peace/inte...
github.com/mission-peace/inte...
Captions Autogenerator: My name is too sharp😂😂
czcams.com/play/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3.html
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.
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! :)
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]
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.
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
Nice Video Tushar !!! Thanks a lot for taking time and sharing your knowledge.
Awesome explaination!!! Keep up the great work buddy
Excellent explanation . absolutely loved the blackboard style teaching.
Thanks for your video, great stuff
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.
Great video.Need more on dynamic programming with some code descriptions.
As always, love Tushar's (the master dynamic programmer!) videos.
great video:) the way u depict how the matrix or array gets filled solves everything for me.. writing the code becomes cakewalk thnks :)
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 .
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.
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?
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.
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 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.
You always makes dp easy for us
bhai tu GOD hai Massive Respect
In the code sample on github, shouldn't "for(int j=0; j < arr.length; j++){" have the middle condition of "j < i" ?
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.
I am thoroughly enjoying your explanations.. Thanks a lot.. Great work.. Spell correction: Mimimum -> Minimum
Tushar: "Yes, we'll use Dynamic Programming to solve this problem"
Me(Beginner): "Why the fuck he is choosing DP? Care to elaborate?" :|
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)?
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?
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't we find the max of the elements of subarray which we can jump and jump to that position
🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
waiting for ur new video ...
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,
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.
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
Hello Tushar, At index 4 value is 2 so it should be two jumps and not 4 jumps right ?
Could you explain the O(n) approach as well? thank you
good solution using dp , thanks for the video
everything is temporary but watching video of tushar Roy after stuck in DP problem is permanent.(100th comment is mine)
czcams.com/play/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3.html
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.
yes we will use dynamic programming to aolve this qn.
EPIC
Tushar is the God of Dynammic Programming.
Very well explanation sir🙏
Best solution is in O(N).
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.
- problem desciption -
So how do we solve this?
yes, we will use dynamic programming to solve this
you should have told naive approach for all the questions before the dp approach
You could have used Greedy Algorithm too! That would be a more efficient solution!
greedy will give wrong solution.
fantastic. tahnks
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 explanation
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.
sir you are the best
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
very helpful
thanks Tushar. this can done cleanly using 2D matrix.
How?
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
I think we can also use BFS to find min jumps.
Yes, that would be the best approach to solve this problem.
Thank you Tushar
'Yes we will use dynamic programming" 😎😎😎
U the best
Much more easier solution:
public int jump(int[] A) {
int max=0;
int e=0;
int sc=0;
for( int i=0;i
Hello Tushar I can't understand ur egg dropping problem....
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;
}
}
What if we have -ve number ?
You need more explanation man on why to use DP n all.
I dont get the table to equation portion. Can anyone help me?
This method will yeild TLE . best approach is Greedy Ladder approach.
Thank You
What if there are negative numbers in the array?
Bruh 😂😂
😂
How u came to know that this problem is D.P problem..??
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.
czcams.com/play/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3.html
my brain hurts
There is a linear solution to this problem which uses a greedy approach
I kindof understood nothing ...
Can you please upload o(n) solution
can we solve it in O(n)??
yes...you can do that with greedy algo approach
@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.
Whiteboard expl very useful
czcams.com/play/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3.html
There is O(n) solution for this problem - BFS
Could be done in O(n), slow solution
why is this so complex ???
This problem can be solved in O(n)..
hholy shit. how?
U can solve it in o(n)
czcams.com/play/PLzffTJx5aHaT-0K_b47KxScckZfDXAKF3.html
Need O(n) Solution..!!
isko kuch aata bhe h? Raat ke aaya hua lagta h ye
nothing clear
O(n) !!!!!!!!!!
What?
THis approach gives TLE
***** This can be solved by greedy approach also.....
bade aaram se
Bhhhhhhh
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??
sala ratta marke aaya hai
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
Noob solution!! .. Give us the O(n) solution
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 czcams.com/video/WyIDphqyUCU/video.html
the guy doesn't has teaching acumen. poor video. wish Aditya would have made this video
Ur English so irritate aap engrejo vali English kyo bolre ho kya jaareurat hh iski normal bi to bol skte go