Climbing Stairs (LeetCode 70) | Full solution with animations | Dynamic Easy | Study Algorithms

Given a staircase with n steps, we need to find the total number of distinct ways to climb it by taking 1 or 2 steps at a time. Sure, this can be done by a brute force method and finding all the possibilities, but there is a really easy way to understand this. This video shows how you can form building blocks and ultimately arrive at a very efficient solution. To make things easy, there is also a dry run of code in JAVA.
Chapters:
00:00 - Intro
01:36 - Problem statement and description
04:51 - Brute Force Method
07:28 - How to understand and attack
09:41 - Finding an efficient solution
12:19 - Dry-run of Code
14:45 - Final Thoughts
Actual problem on LeetCode: leetcode.com/problems/climbin...
📚 Links to topics I talk about in the video:
Dynamic Programming: • Dynamic Programming ea...
Brute Force Solution: • Brute Force algorithms...
What is Big O?: • Big O Notation Simplif...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

[@pcccmn]

I have watched NeetCode, CS Dojo and Kevin Naughton's explanation but couldn't understand the concept behind arr[target] = arr[target-1] + arr[target-2] for this problem until I came across your "How to understand and attack" segment. Thank you for explaining like I'm 5.

[@Arcadencebeats]

I had the same issue. He explained it so much better!

[@edoreemmanuel4250]

I am just seeing this..I love the explanation...lols....

[@testing-js8iu]

yes you right

[@horcruxone]

Handsdown the best explanation available on youtube for leetcode 70!

[@Ranjan-xc5nl]

Provides sound explanation of algorithmic approach and solution, indeed worthy channel. Thanks.

[@dirtbag1126]

Great video! Loved the visuals. You did an excellent job at breaking down the steps needed to approach this problem. Keep it up!

[@nikoo28]

glad you liked it. If you want to see more content like this, consider joining my channel: kzbin.info/door/T-S2ngqEBoYCM5UKuNeELgjoin

[@jamjam3448]

Wowww. Thanks a million bro. After watching many turotials on this, yours is the best! I've understood it! Thanks

[@niktri6805]

Really excellent explanation, the breakdown of the problem made it much more easier to understand.

[@vichitrakalakaar]

I tried to solve this problem using recursion but TLE.... And you just gave me best solution .... Thank you so much guru🔥💯❤️🙏

[@yousefnegmeldin5903]

Thank you so much, you helped me understand dynamic programming with such a simple explanation and example.

[@sa35085nhs]

I read one of comment which was recently posted, but u replied to that comment also,great !!!

[@zb2747]

Man great breakdown. I'm doing interview prep by grinding on leetcode and your videos have been a great way for me to understand how to solve set problems. You do a great job of talking slowly but not too slow and breaking the problem down that is simple to understand.

[@priyagupta5139]

same here

[@srikarjonnala6509]

such a lovely solution and explanation

[@purnachandrasahu622]

This was really helpful!! Keep up the good work..

[@kunalchauhan5294]

Thank you soo much this is my 1st dp question I'm glad i found good description of it thank a lot you are a great tutor

[@fourieruddin871]

Your excitement for teaching has no bounds 🙏

[@nikoo28]

thanks for your kind words

[@ajaygunalan1995]

Dude, you nailed it. LOVE YOU!

[@nikoo28]

Glad you enjoyed it 😄

[@susmitobhattacharyya1668]

Thanks for your simple explanation.

[@user-wg6nk7ix7x]

Man great breakdown of this problem, simply the best!

[@arjunb9342]

Thank you so much... Best and Easiest explanation ever .

[@dailyprograming9003]

your explanation skill is too good

[@nerd6134]

If this guy makes a math course it’ll be one of the best.

[@ankithareddy4497]

true..and everyone will start coding.

[@sukanyaghosh24]

Omg such an amazing explanation, thank you so much sir 🙏❤️

[@kasifmansuri7552]

Great explaination!!

[@tiyashasen5020]

You teach amazing. Thanks for making us understand difficult concepts in a simple way🙂

[@nikoo28]

Glad you feel this way :)

[@vasavi5908]

Great explanation.Thank you very much

[@vsh-torch]

Good one, bro. Thank you.

[@ParmodYadav]

Very good way to teach brother very depth understanding of the question very good

[@rubylnic]

thank you for the great explanation!

[@gauravkumar-ek8mr]

Adbhoot. Love your explanation

[@shortme9374]

Hey Nikhil, I really liked your way of explanation. keep making such videos. Subscribed.

[@nikoo28]

Thanks for the sub!

[@kavinsanthosh1306]

Great explanation! This is my first DP, Memoisation Problem!

[@nikoo28]

you are gonna love dynamic programming. Check out House Robber as well. kzbin.info/www/bejne/jInUhoSPfLKhh8k

[@ram_mandir_india]

The way you explained it made it so easy to understand. Thank you, my friend, for helping me in my first dynamic programming question. Love from Haryana.

[@nikoo28]

You're very welcome!

[@_Adil.Khan_]

I will say just fantastic!

[@minecraftredstoneinspiration]

Really well explained.

[@Rajendrachoudhary-ut8ll]

Awesome explanation

[@yashthakur5712]

hats off to you sir, excellent explanation, and thnks a lot

[@rinkishaw1929]

Great video ❤

[@kuoyulu6714]

just starting my leetCode journey, with no math background, this video helped me so much, thanks a lot!

[@nikoo28]

I wish you all the very best :)

[@kuoyulu6714]

@@nikoo28 thanks!

[@codeflix927]

it's Amazing explanation . I loved it.❤❤❤❤❤❤❤❤❤❤❤❤

[@AkashYadav-di6kd]

Thank you very much, sir.

[@RakshithVrishab-ht8vk]

The best explanation i have come across, i have watched other videos of same problem from other instructors , their explanation was also good, but Nikhil the way you've explained is so simple and top notch, thank you very much

[@nikoo28]

really glad you feel that way 😄

[@hommy4850]

well explained thanks you!!

[@Deepz007]

Yours was the best explanation.

[@sammedpatil3907]

very nice method of explanation....

[@ritendahiya8828]

Thank you sir!!

[@kunalkheeva]

great content!

[@apuravsharma9995]

Great explanation

[@priyagupta5139]

Your Explanation is very good.

[@nikoo28]

Glad you think so!

[@Mr.Zeus11]

Thank you so much, first time while I saw the problem, i was like WTH how I am gonna solve this. After seeing your video it's so easy!! ❣

[@nikoo28]

Love it!!! 😁

[@MrMichalXXL]

I was skeptical but in the end you delivered the understanding

[@nikoo28]

glad i could help you

[@sreeharsharaveendra289]

Best explanation behind the thought process of approaching the problem. I think we can reduce the space complexity to O(1) because we just need to return the value for the number of ways to reach the nth step. So a sliding window approach can also work, which is kinda similar to dynamic programming, but you don't memoize all values, just the previous 2 values and keep updating it.

[@nikoo28]

Excellent

[@TaufeeqAhmed-hk4rz]

Awesome Explanation bro

[@nikoo28]

Thank you so much 🙂

[@1tav0]

I wish you could have been my teacher for dsa! You are a true teacher, this was so simple to follow I want to cry. Thank you so much sir! Please keep making this type of videos they are life savers for people like me! Thank you thank you! Please could you touch upon recursion and tree problems please !

[@nikoo28]

Thank you so much for your kind words. I do have videos on recursion and tree problems. Check out my playlist on algorithmic paradigms. :) I hope they are helpful too.

[@santoshibora1892]

@@nikoo28 why array is of n+1 size, why cant n??

[@krishkhemani96]

​Bcz index starts at 0 if you want to calculate the 8 step you need ans of 8th index but if u pick array of size n you would be providing ans of 7th index instead of 8​@@santoshibora1892

[@kanimozhikani7138]

Thank you so much sir🎉

[@data10xwithsandeep]

Boss you are a king of coding and the best teacher

[@nikoo28]

Thank you so much

[@user-qy2fm3pu2b]

great man...!!!!

[@mohitarya5189]

Thank you 😊😊

[@latest_news_stories]

Lit 🔥very well explained

[@nikoo28]

You too are awesome 😎

[@omarkhan5223]

Great video, what tool are you using with your pen to make those bright red lines?

[@nikoo28]

that is an application called GoodNotes 6

[@carlosraul6578]

Thanks my bro

[@nikhilmishra8266]

observing the output we can also use simple fib program

[@adnaan28]

just an amazing explanation

[@nikoo28]

Glad you think so!

[@Arcadencebeats]

Thank you so much!

[@nikoo28]

You're welcome!

[@SHAIKAFTABAHMED-gz9wu]

Bro u r really a bro ....

[@abhishekkeshri3974]

you make me fall in love with dynamic programming .please do a live talk with us and give some advices for interview . thanks for the video nikhil.

[@nikoo28]

glad you liked the video. Check out my latest video on Edit Distance too. Just uploaded it today :) I will have a youtube live coming up soon.

[@abhishekkeshri3974]

@@nikoo28 glad to know. We like to talk with you.

[@rishabhsinghal5823]

very nice explanantion baat to hai..

[@TrueRDX]

thanks very much for explain dp 🤗

[@nikoo28]

Thank you so much 😊

[@sathiroy4788]

Nice explanation.

[@nikoo28]

Keep watching

[@filmbuzz9419]

Nice

[@rajnishroy7429]

thank u..

[@jritzeku]

Is it bad to use recursive solutions for dynamic programming? I simply used recursion similar to fibonacci and then to make it more performant used a memo obj. That way it will avoid recursion for already encountered inputs. The tabulation approach seems lot less intuitive for more complex problems.

[@nikoo28]

I won't say bad to use recursion but it is definitely less intuitive. When something goes wrong it is very hard to trace what happened, and fixing it becomes problematic. Recursive solutions look small for sure, but it is not necessary that they take less space as well.

[@abhishekkr8077]

Bahut badhiya padhate ho sir aap 🙏

[@nikoo28]

thank you so so much

[@DeveloperJay]

the way of explaining was very very good. but we can use simple Fibonacci approach as well.

[@nikoo28]

but how would you know that it is a fibonacci sequence??

[@omkarkhandalkar8869]

Really helpfull sir The way you're explaining is >>>>>>>>>>>>>>>>>>>>>>>>> any other course or youtube channel

[@nikoo28]

It will be so helpful if you tell about my channel to your friends/colleagues as well 😃

[@omkarkhandalkar8869]

@@nikoo28 yes sir shared with community groups

[@agentphoenixtm642]

Isnt this is tabulation rather than memoization? As we following bottom up approach from base case to final result 13:37

[@nikoo28]

by tabulation if you mean storing all results in a table, then yes it is the same. Memoization is just a concept to store your calculated results, you do it in any data structure you like as long as you are saving space/time.

[@ujjawaltyagi3095]

why +1 i didn't get it ? isn't it like prefix sum? so we are basically storing sum of last two ele so why we need n+1 size instead of n ?

[@nikoo28]

that is just to avoid index out of bounds exception

[@prashanthshetty8337]

This can be done using 2 ints as well. ```golang func climbStairs(n int) int { if (n == 1 || n == 2) { return n } a, b := 1, 1 for i := 2; i < n; i++ { a, b = b, b + a } return a + b } ```

[@skrishnan9625]

This problem can also be done with the help of recursion

[@Muhammed___koya]

but if the no of stairs is 1 your code will cause indexoutofboundexception. In order to avoid that you should initialize 0 index value and 1 index value to 1 and run the loop starting from i=2;

[@shivashankar6043]

So, its a modified question of finonacci series problem

[@nikoo28]

not exactly...it just happens to have a fibonacci pattern.

[@CostaKazistov]

Confused. Isn't this LeetCode 70 (Climbing Stairs) and not 47 (Permutations II)?

[@nikoo2805]

Thanks..this has been fixed :)

[@astra8072]

so solution of this problem is basically a fibbonacci?

[@nikoo28]

you are absolutely correct. Watch another fun video on fibonacci series: kzbin.info/www/bejne/jaawhXaXgpejoZo

[@sudippaudel1364]

On How to understand and attack, how can (climb 1 stair from step 6 + climb 2 stairs from step 5) be translated to (number of ways to reach step 6 + number of ways to reach step 5)? HOW?

[@nikoo28]

that is because you have to find the total number of ways. if you are able to reach step 6, then with 1 more stair you will reach step 7. so if you can reach step 6 in 10 ways, you can reach step 7 also by just climbing one more step. so all 10 ways you reached step 6 and then 1 more stair. so you are reaching step 7 in 10 ways. similarly, if you reach step 5 in 15 ways, then with just 2 more stairs you will reach step 7. so you can also reach step 7 in 15 ways. total ways = number of ways to reach step 6 + number of ways to reach step 5

[@sudippaudel1364]

Thank you @@nikoo28

[@riyamalhotra6726]

I understood how to implement the code and I used recursion, like this:- public class Solution{ public int climbStairs(int n) { return fib(n); } public int fib(int n){ if(n

[@brunosdm]

That will have a LOT of redundant method calls, but you can keep the recursive approach if you use memoization. Look that up. There's also videos explaining this solution with that approach.

[@riyamalhotra6726]

@@brunosdm Oh! I looked up memoization and watched the explanation by hackerrank. Thanks!

[@nikoo28]

absolutely correct, with memoization you can store your results..so you are not computing again and again.

[@machans-203]

You can reduce space complexity to O(1). It's a fibonnaci series in other name👍

[@nikoo28]

But you need to understand the problem before you can derive the fibonacci series

[@sukanyaghosh24]

Sir please make a series of all the 150 neet code questions using java, it's a humble request 🥺

[@nikoo28]

Will upload soon

[@sukanyaghosh24]

@@nikoo28 thank you ☺️

[@filmbuzz9419]

Min Cost Climbing Stairs also make vedio on these quation

[@nikoo28]

let me find it

[@sanketsuryawanshi]

Sir please make whole series on Tree,Graph, DP plz sir

[@nikoo2805]

Hi, check my playlists on the channel. Currently I am trying to add as many videos as I can…but just limited by the time I have available :)

[@sanketsuryawanshi]

@@nikoo2805 Thanks sir no problem

[@nikoo28]

The complete playlist on graphs is now available: kzbin.info/aero/PLFdAYMIVJQHNFJQt2eWA9Sx3R5eF32WPn

[@Kemba_oak]

this feels exactly like Fibonacci sequence

[@nikoo28]

Yes, but you need to arrive at that conclusion first

[@sarthakjoshi21]

op

[@anishbhandari4699]

why array size is n+1

[@nikoo28]

you need to start from 0

[@anishbhandari4699]

@@nikoo28 but you are not using 0th index right

[@gnanaprakashm843]

11:44 n minus 1 and n minus 2 😅😅

[@amitdahal9053]

Thank you bhai...apke tasveer print karke main kal se pooja karunga

[@nikoo28]

thanks for the lovely feedback 🙏

[@rickdutta3935]

This is just a fibonacci series answer.

[@nikoo28]

but you need to reach over there first :)

[@rickdutta3935]

@@nikoo28 Love your videos sir❤

[@melk48111]

you should make a udemy course and make $$

[@nikoo28]

Haha..what course do you think I should make?

[@melk48111]

@@nikoo28 Udemy course on solving leetcode and another course on DSA

[@TECHNICALMANedit]

this method is right or wrong @NikhilLohia when i submit the code then I give's exceded time error if(n == 1 || n == 2){ return n; } int recCall1 = climbStairs(n-1); int recCall2 = climbStairs(n-2); int smallCal = recCall1+recCall2; return smallCal;

[@nikoo28]

try debugging with edge cases

[@TrueRDX]

sub done 🤙