Jump game | Leetcode #55 | Valley peak approach

This video explains a very important programming interview problem which is to find if it is possible to jump indices of an array and reach the last index of array or not. We have some given constraints which are, we can't jump from 0 valued index and that we always start at index 0. I have shown the solution using backtracking intuition and a very beautiful observation using valley peak approach. I have taken easily comprehend-able examples and finally explained the code for the same. As usual, CODE LINK is given in the description below. If you find any difficulty or have any query then do COMMENT below. This problem is from Day 25 of the leetcode 30 days April coding challenge. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

[@techdose4u]

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
🔴 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/

[@preetibatra208]

To the world you may be just youtuber , but for us(learning geeks ";) you are the hero!! great work...

[@techdose4u]

Thanks for your appreciation 😅

[@rajatmishra6628]

🙌🏻🙌🏻

[@MadForCs16]

I thought you would say *To the world you may be just youtuber , but for us(learning geeks ";) you are our world!* xDDD

[@varunsadhu9060]

Dude, I made the mistake to look for a solution for this from other videos. But i must say i could only understand it by your explanation. Keep up the good work buddy.

[@techdose4u]

Thanks bro :)

[@algorithmimplementer415]

I could not appreciate you more for your initiative of making video each day. BIG THANKS.

[@saket9363]

Thank you so much for all your videos! I am learning a lot!
Just one quick suggestion!
Can you please show the actual Leetcode question at the start of the video? It would be really helpful! Thanks once again!

[@techdose4u]

Actually the questions are easy to understand with lower constraints. So it would be very easy to understand. I read the questions first if it has more constraints.It saves TIME in video length 😅

[@syamprasadupputalla8233]

Bro, trust me this is some serious content. So far, I have been solving problems with a different mindset and you blew me up. I have seen a lot of videos on Leetcode solutions, but never seen something like this, and explanation is very clear. Thank you so much brother :)

[@f3-faithfitnessfinance]

Few more subscribers away from 10k!
Congratulations in advance!🤘🙌
This is just the beginning 💪😎

[@techdose4u]

Thanks bro :)

[@AdarshSingh-vt4kw]

It would be much better if you also tell about the minimum number of steps required to move to at the end of the array

[@soumitadalal6130]

The concepts you teach are so useful that I am bound to adore your vedios.. Keep teaching us like this.. And thanks a lot man..

[@techdose4u]

Welcome :)

[@ersinerdem7285]

wow, just wow! only thing I could add would be, exiting early after the reachable calculation by checking if you can reach the end.

[@Code_Solver]

What an Explanation. Give a big round of Applause to this sir...

[@rishabhpathak9916]

What an amazing teacher you are! Thanks a ton!!

[@techdose4u]

Thanks bro :)

[@shashankmehul02]

You are great man. Such simplification really helps a lot sometimes.

[@techdose4u]

Thanks :)

[@PersistentProgrammer]

Great explanation. I solved the same question today. I have linked your video in my description.

[@techdose4u]

Thanks :)

[@shridharsarraf2188]

Surya pratap sir, jab bhi leetcode se frustrate ho jata hun aapke videos dekhta hun. Aap itna calmly koi bhi problem batate ho aur that also calms me down. Lekin kya karun sir dp hai bhi aisa topic ki itni practice ke baad bhi basic medium questions bhi rula dete hain

[@ManjilAshaman]

this solution is just a master peace and you the master 🙌

[@unlockingitpotential575]

Your explanation understood KG level student ,that's a great work

[@abhijeetbhowmik2264]

How do we derive such methods on the spot. I tried this with recursion. Got TLE. Then tried maintaining a list which tells me what index I have already reached out to in previous recursion step to skip it. Then also TLE. And then here it is. Done in O(n). How to achieve this sort of critical thinking. You are awesome.

[@rhinoara7119]

Another good approach with O(1) complexity will be start searching for 0 from ending of the array, when a zero is found check next number is greater than 1,if not check if its next greater than 2. Return false if this condition fails until index 0

[@Jyotigupta-vs4mz]

Hello Tech dose sir,Small corrrection in For Loop i should be i

[@RaviYadav-xg2hy]

we can also start from ending index of the array and keep updating the required jumps(starting from 1), and finally check for the first element if it has the required number of jumps !!

[@techdose4u]

Yes correct. Both ways are same only.

[@MarcoBiedermann]

You could also loop backwards in order to figure out if the last position is reachable
```ts
function canJump(nums: number[]): boolean {
const { length } = nums;
let lastPos = length - 1;
for (let i = length; i >= 0; i -= 1) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos === 0;
}
```

[@techdose4u]

Yes.....anyone is correct.

[@haydnmurray6998]

I see this solution but worst case for both solutions is O(n) so would we count these as the same?

[@techdose4u]

Yes true.

[@amanbansal97]

It will take less time to complete because there is no comparison of max

[@charanpasupula3763]

After for loop I think we still need to have another if condition to check if reachable >= array.length - 1
otherwise this code is failing for the case of [1,0,1], do correct me if m wrong
edit: I was wrong in writing this condition in for loop i < array.length - 1 , it should be i < array.length

[@manjunathp9466]

Python solution
class Solution:
def canJump(self, nums: List[int]) -> bool:
if 0 not in nums:
return True
reachable=0
for i in range(len(nums)):
if reachable

[@techdose4u]

Thanks for sharing 👍 Please keep sharing Codes in Python.

[@ladydimitrescu1155]

Can you explain the purpose of if 0 not in nums:
return True?

[@vibhasyadav6491]

@TECH DOSE please make a video on minimum jumps to reach the end.

[@codingwithneeraj1305]

exceptional approach have you thought of this approach on your own??

[@gurpreetchawla2066]

Whenever i am not getting clear Explaination of a problem in other channel , i jump to this channel and you solves it in such a way that anyone can understand comfortably .
You got the way of "How to Teach so that anyone can understands".

[@techdose4u]

❤️

[@rajendertanwar1881]

This explanation truly deserves ❤ 👍

[@techdose4u]

Thanks :)

[@paragroy5359]

Nice explanation sir...thanks for the video

[@techdose4u]

Welcome :)

[@mystryb345]

Bro your every video has very good explanation.It is easy to understand

[@techdose4u]

Thanks

[@6priyanshu]

very well explained...please keep uploading more such video's.....such explanation makes coding easier and interesting..thankyouuuuuuuuu

[@sagarksahoo4667]

explanation was very crystal clear, good work

[@techdose4u]

Thanks :)

[@nikhilkumar-ot9rn]

awesome explanation!!!! can u start a platform where u take questions from us and solve it ...please..

[@techdose4u]

It's already ON. I am putting questions which are already requested.

[@nikhilkumar-ot9rn]

@@techdose4u ok then, could you please solve Educational Codeforces Round 53 (Rated for Div. 2) problem c (vasya and robots) also could you please solve longest palindromic substring using binary search .

[@AKASHSINGH-td7wx]

can you please give me the code of that backtracking approach u mention at the beginning...?

[@venkateshthirunagiri85]

Make a video on your TH-cam kit like video editors, softwares, Mike u use to make TH-cam videos .......... 🎥🎥

[@techdose4u]

Nice idea :)

[@sajithtm4864]

Great explanation. Glad to see you posting more videos on DS.

[@JgNt3981]

How do you get the logic for the problems sir, that too simple one. 😱🙏 please share if you could.

[@vivek.tiwary]

How many problems you solved to get the depth of this kind of problem? No one explained like you did. Thank you

[@dhanashreegodase4445]

I have no words to say ..lovely excellent video

[@techdose4u]

Thanks

[@venkateshthirunagiri85]

We or you are going to Hit 10k subscribers by tomorrow 👏👏👏👏

[@techdose4u]

We offcourse. Tommorow I will come LIVE to thank our community for continued support :)

[@venkateshthirunagiri85]

@@techdose4u you deserved it 😎

[@techdose4u]

Thanks :)

[@fullysimplified7139]

I can never thanks you enough as thanks is such a small word
I wish you all the best in your future journey

[@ekengineer9868]

So cool explaination!
Impressed 🙌

[@avinashpatil9662]

good explaination..totally understood the problem and its solution.

[@techdose4u]

Nice :)

[@KaranDoshicool]

How to calculate number of steps?

[@techdose4u]

Store it when you find a path. Keep updating on each call.

[@swatibabbar9953]

How to find minimum jumps to reach end of array with this code?

[@rakshith3547]

Even i had the same question

[@hinata4661]

please upload the min jumps problem using dynamic programming. If already uploaded please share the link

[@navinshyamkuwar9401]

Very Good Explanation.

[@deepaksingh3533]

i can go for solution only when i get what exactly a problem is, after watching this i still not able to understand what exactly this problem is asking.

[@tareqdevdiary]

No explanation can be better than this.

[@shubhamkumar-hx1fb]

if you think so then you are leaving in some virtual world

[@tareqdevdiary]

For me it's the best explanation. I've understood the solution after watching this, before that I watched multiple videos from other youtubers but have found this one the best.@@shubhamkumar-hx1fb

[@suryakiran2970]

last approach super

[@techdose4u]

👍🏼

[@toekneema]

Best solution ever

[@techdose4u]

Thanks

[@kollivenkatamadhukar5059]

Can you please guide me on how to approach a problem, I always try to solve a problem but will fail in between and after seeing your explanation after enough trails I feel like this can be done but why I didn't.

[@techdose4u]

This requires practice. Don't give up. I was in the same position as you. I struggled and invested a lot of time before I reach to my current position. Even now I face the same problem solving the harder problems but I take the same approach for solving.

[@AruneshSrivastava]

We dont have to loop through the entire array in some cases . like [1,3,2,0,2] ... in this we can reach end at 2nd index itself , we can have a check like -- if (reachabe == n ) retrun true . save some time maybe

[@techdose4u]

If you increase checks then actual time will increase instead of decreasing.

[@SonuKumar-kj6uz]

Please upload minimum number of jumps to reach end....🙏🙏

[@NipunAggarwal-h9l]

its very easy and cool explanantion

[@praphulyadav4471]

sir your explanation is awesome it becomes so easy to understand❤️👍

[@techdose4u]

Thanks :)

[@scarywitcher]

finally understood brother. thanks to you

[@akshatchouhan5199]

Buddy can you explain this question using DP

[@alltechsimplified2134]

how you come up with these approaches

[@monishnjs]

Wow, what a nice solution...thanks

[@techdose4u]

Welcome :)

[@indrajith2002]

bro you really explain with clarity just love it .Keep going

[@Safar_Ayushi_Ka]

Sir please make video on min jumps using DP

[@techdose4u]

Yea sure. I told you in this video that I will include it in future. It is jump game 2. I will do it don't worry.

[@bestdeal3385]

thankuu sir you made this very easy 😃😃

[@techdose4u]

Welcome 😀

[@willturner3440]

You again proof you are great, love u bro

[@creatorstudio5945]

Amazing explanation sir :))

[@mmsamar1007]

can you write the brute force code

[@techdose4u]

Yea

[@harshpatel1385]

After this series plz make video on how to crack codevita exam

[@techdose4u]

Achha okay. I need to see it once how is the pattern.

[@PrashantSingh-pg9vq]

should we bow? yes, he is a king !! ...

[@techdose4u]

😂

[@575saisri4]

sir, u r really the best.. thank u so muchhhh..

[@techdose4u]

Thanks Sai :)

[@Utkarshgg]

reachable

[@ayushdhiman8128]

leetcode have one test case i.e. [2,5,0,0] and by my own approach I stuck at this. isn't this test case wrong?

[@vaibhavgaur8200]

JAVA Solution:
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int reachable = 0;
for(int i=0; i

[@techdose4u]

👍🏼

[@swami1016]

well explaind

[@techdose4u]

Thanks

[@saunaknandi1814]

Is valley peak a greedy approach?

[@simmi641]

To the point explanation thank you ❤

[@alex-gz7ud]

Awesome explanation!!!! You saved my day!!!

[@techdose4u]

Welcome :)

[@emmatime2016]

Great explanation! Thank you!

[@techdose4u]

Welcome :)

[@rbk.technology4747]

Really amazing

[@mausami16mau]

well explained. thanks :)

[@techdose4u]

Welcome :)

[@AdityaRaj-ey6tq]

how is [2,0,0] coming true

[@sandeepnallala48]

Sir for this q dp is not necessary right?
I did the q of min jumps to reach end of array , and tried this in similar wau, but getting tle in leetcode, maybe some code mistake.. this simple method is good sir. Sir have you started dp sir?

[@CHIRANJIBNANDY1]

Dude... just an awesome explanation.

[@techdose4u]

Thanks :)

[@dimpleshah3037]

Superb explaination....

[@techdose4u]

Thanks :)

[@monkeytrollhunter]

I am here after my recursive solution timed out

[@AdityaPratapSingh-ss8wg]

Same here

[@sonumondal9376]

Yeah becoz it is 2^n so tle

[@jaydeepmahajan6598]

This is eventually dp because we are first checking for smaller inputs 😅, am i right ?

[@techdose4u]

Yea 😅

[@mystryb345]

Bro plz cover what min jump array also

[@techdose4u]

Okay.

[@thehorizonreport]

Literally amazing hero

[@techdose4u]

Thanks

[@rajbhushan3541]

good explanantion

[@avishekarora]

That's a really god solution

[@hoyinli7462]

excellent explanation

[@techdose4u]

Thanks

[@reshwanthroyal2601]

class Solution {
public boolean canJump(int[] nums) {
int reach = 0;
for(int i =0;i=nums.length-1)
return true;
}
// if we cant reach
return false;
}
}

[@liftwithamey]

could you please provide recursive/backtracking code?

[@techdose4u]

I will make separate recursion video when I start backtracking.

[@liftwithamey]

I will be waiting!!!

[@pritishpattnaik4674]

Very much well explained

[@yaswanthp2294]

Again excellent explanation

[@letsdoeverythinginoneweek9398]

how can we find max jumps to reach at end of array

[@rohitkanojiya5880]

Sir, Great Explaination Thanks

[@techdose4u]

Welcome

[@bhopalsingh4102]

I tried using memoization... i got TLE for a testcase having values as [24500,24499,24998,24997,24996,....].

[@techdose4u]

I din't try memoization but simple recursion. I passed 70/75 tc. So I applied the efficient O(N) approach 😅 DP will also work.

[@bhopalsingh4102]

@@techdose4u same here..
BTW.. excellent explanation👍👍

[@mayanksikarwal8431]

Wonderful

[@techdose4u]

Thanks :)

[@retro-re-play]

This problem is much simpler if you start checking from behind:
Use formula: if nums[i] >= len(nums) - 1 - i
To see if you can reach end of nums from an index i.
Start iterating from the end-1 and check if you can reach the end from i index, if yes then mark the i as the end (slice the nums = nums[:i+1]).
Now in furthur iterations you need to check if you can reach the new end, if yes again update the end.
If any point in loop if you can reach end from i, and i == 0 then return true

[@Danish-saifi1]

How to slice

[@funtalk4083]

Thanks sir. Great explanation.

[@techdose4u]

Welcome :)