Climbing Stairs | LeetCode 70 | Google Coding Interview Tutorial
Vložit
- čas přidán 26. 07. 2024
- Climbing Stairs solution: LeetCode 70
Code and written explanation: terriblewhiteboard.com/climbi...
Link to problem on LeetCode: leetcode.com/problems/climbin...
Buy Me a Coffee: www.buymeacoffee.com/terrible...
AFFILIATE LINKS
If you're interested in learning algorithms, these are great resources.
💻 40% off Tech Interview Pro: techinterviewpro.com/terriblew...
⌨️ 20% off CoderPro: coderpro.com/terriblewhiteboard
💲 All coupons and discounts 💲
terriblewhiteboard.com/coupon...
Climbing Stairs | LeetCode 70 Google Coding Interview
#climbingstairs #leetcode #algorithms #terriblewhiteboard #codinginterview
Click the time stamp to jump to different parts of the video.
00:00 Title
00:06 Problem readout
01:01 Whiteboard solution
10:52 Coding solution
23:30 Result and outro
Your teaching style is super helpful. Not just the way you write everything on the screen, but the way you use emphasis and inflection with your voice for certain phrases and words. The audio and visual presentation is spot-on.
I have one question about this problem. At 19:38, you wrote on-screen that the map contains 1:1.
How does the map have any values stored at this point? The recursive call on the right side of the '+' sign hasn't been executed yet, so we have:
storedResult[1] = 1 + countingFunc(stairsRemaining - 2, savedResults).
I'm not understanding how that would set storedResult[1] = 1.
Maybe it's me misunderstanding recursion. And sorry if my question is confusing. I find leetcode problems incredibly hard to begin with (even the easy ones!)
Hey, thanks for the compliment.
You're totally right about that. At that point, since the other side hasn't executed yet, it isn't saved to the map. Only after the other side executes does it add the 1 of the left side to the 0 of the right side and then saves that to the map. I'll pin your comment and my response to the top of this video if you don't mind.
@@TerribleWhiteboard Sure! I had another question (more of a general question about leetcode):
I can grasp the solution after watching your vids, but I wouldn't have come up with a solution by myself in a million years. Before watching this video, I had a pencil and paper in front of me for 30 minutes, and I had no idea how to approach it. Couldn't even get 2 lines of code written down. How do you come up with solutions on your own? Is it just a matter of practice?
@@all20790 Yup. Just practice. If you get stuck on a question for too long (which for me is more questions than I'd like to admit), just give up and look at the various solutions from leetcode/youtube/whichever resource you like best. Then take those concepts, understand them inside and out, and then apply them to future questions. You'll see the same patterns popping up over and over.
@@TerribleWhiteboard that's great to hear. Cheers.
this! I look for his videos first whenever i have problems solving algorithms
Thank you. EXCELLENT explanation!
Interview prep is such a grind sometimes... When you have questions about a problem and you can watch a 25m video and come away crystal clear.. its invaluable
It seems strange that this is marked as an easy problem on leetcode. It's the type of problem that wouldn't be readily solvable unless you have specific experience using trees to solve combinatorics. This may just be my inexperience with the type of problem, but I would rank this as hard compared to other leetcode problems. Thanks for the great explanation.
Thanks! Yeah, I think this should be about a medium. Not quite hard because once you've seen questions like this a couple times, you get the hang of it, but not necessarily easy.
I think it's marked easy due to the fact that this is really just a fibonacci sequence problem, which is commonly taught when learning recursion or dynamic programming & memoization. It's tough the first time, but once you understand the concept it's really just about applying it to other problems
please keep this up. you are a really good teacher.
viewing the problem as a tree problem makes things so much clearer! But there is one thing that confuses me, why does a-1 makes it not a valid path. What in the code says -1 =! valid path If you get -1, the should the function not return 0; in which case, it would be similar to the other cases where there is a zero.
Maybe I'm using sloppy wording. When I say valid path, I mean a path that increments the total by one. For instance, if we have a path where there are 0 stairs remaining, that path is "valid" and returns 1 (increments the total by 1). A path with negative stairs remaining returns 0, so it doesn't affect the total. If I'm not answering your question, let me know! If people have questions, it means I need to be more precise in future videos.
@@TerribleWhiteboard that makes sense. i am probably just slow on the uptake, recursion still confuses me a bit. but that makes sense, if it is returning 0, then your adding nothing and thus not climbing. Thanks for the clarification.
Thank you for pointing out that what they are using in the solution is how many steps 'left' not how many steps they have to go. I was confused why they counted as 1 when they have equals number for current step and destination step. You have a great teaching skill!
Just wanna say you're the best! Coding has not been that hard with your help!
Thanks!
Super clear explanation!
Nice solution indeed. What would be the complexity of the solution?
Time complexity should be O(n) since you're visiting each node (if you look at it like a tree) once.
hmm I have doubts about that.
O(n) would be traversing the stairs once (incidentally the problem uses n for the number of steps), not the tree.
The tree has several O(n) paths. The number of these paths depends also on n. However, I'm not sure how many these paths are (and how the map optimization changes the number of full path traversals).
Time complexity is roughly the number of operations it takes to complete the task (I know that's a very simplified definition). It's O(n) because the effort it takes to solve for 2 steps is roughly 2, for 10 steps is roughly 10, for 15 steps is roughly 15, etc. As you're calculating an n of, let's say, 5, you're at the same time calculating the results of 0, 1, 2, 3, etc, and saving them. So the next time you see the same number, you're not doing any extra calculation. You're just adding its value to whatever n you're on at the time. Sorry if my explanation is lacking. If you find anything saying it's not O(n), let me know so I can see where I'm wrong. Thanks!
This was super helpful man. Loved your teaching style. You've earned a subscriber!
Thanks!
Thank you. This is well explained. thanks a lot again.
You're welcome!
thank you so much for explaining the recursive solution!!
You're welcome!
Do we have to do recursion or can we just add the previous two steps together? Thank you for this explanation!
Amazing solution. I had a doubt, I can't get that intuition of solving recursive questions, IDK why, I keep trying to draw it on paper but can't, can you suggest some tips?
Ive replayed this video several times and I just don't see how stairsRemaining became 2 around the 20 minute mark. Its very frustrating lol.
When you return 0 or return 1, how is that result saved into savedResults? I'm having difficulty visualizing the process. It's not like the numbers are saved in the empty object { } of savedResults right?
if you see at line 20, it is saving the the 0 and 1 to the savedResults map. when n = 1, savedResults[1] = 1 + 0 (0 because 1 - 2 = -1). so it saves savedResults[1] = 1
def numWays2(n: int) -> int:
def countingFunc(stairsRemaining,savedResults):
if stairsRemaining