Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
70. Climbing Stairs
Difficulty: Hard Language: JavaScript
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Solution (Recursive with Memoization):
This method might exceed the time limit as testing performed on 3/10/2022.
The key to solve this problem is that you can only climb 1 or 2 steps each time. If it takes 4 steps to get to the top of a staircase, we can climb to either the 1th level or the 2nd level on the first climb. Respectively, we have 3 more and 2 more steps left to climb. And if we already know the total distinct ways to climb 3 and 2 steps, then the total distinct ways to climb 4 steps will be 'total distinct ways to climb 3 steps + total distinct ways to climb 2 steps.' Recursive with Memoization will help us perform this calculation.
const cache = { 0: 0, 1: 1, 2: 2 }
//Initiate a map (note 2) that stores total distinct ways of
//climbing steps of 0, 1 and 2. There are 0 way to climb to the
//top of a staircase with 0 step. There are 1 way to climb to the
//top of a staircase with 1 step. There are 2 ways to climb to
//the top of a staircase with 2 steps. The value can be accessed
//with 'cashe[n].'(note 3)
function climbStairs(n) {
if (n === 1) return 1;
if (n === 2) return 2
//If n equals to (note 4) 1 or 2 then return the total possible
//combinations we already know from the problem itself.There are 1
//way to climb to the top of a staircase with 1 step. There are 2
//ways to climb to the top of a staircase with 2 steps.
if (!cache[n]) {
//'cache[n]' helps us access the staircase we have already
//climbed. If 'n' cannot (note 1) be found in 'cache,' that means
//it is a staircase we have not climbed before. Then we will
//calculate that in the step below and store it in 'cache'.
cache[n] = climbStairs(n - 1) + climbStairs(n - 2);
//With recursion, the calculation will continue until n is equal
//to 1 or 2.
//For n = 3,cache[3] = climbStairs(3 - 1) + climbStairs(3 - 2)
//total possible way to climb 3 steps is subtracting total ways to
//climb 2 steps by total ways to climb 1 step; that we can already
//find in cache { 0: 0, 1: 1, 2: 2 }.
//By performing 'cache[n] = X,' we can store value 'X' in the map
//with corresponding key of n. The update cache will be
//{ 0: 0, 1: 1, 2: 2, n: x }. And if we need to know how many
//distinct way we can climb a staircase with n step in the future
//calculation; we can use 'cache[n]' to get to the value 'x.'
}
return cache[n];
//Find the value in 'cache' with a key of n
}
Solution (Dynamic Programming):
function climbStairs(n){
const dp = new Array(n).fill(0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
//Create an array with n element and filled with 0.
//Initialize 'dp' with some base Cases
for(let i=3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2]
// Start from n=3 since we have covered the solutions up to N=2 above
// Sum the last 2 results behind me to get the current result.
}
return dp[n];
}
References:
LeetCode Problem Link
LeetCode Discussion: dclif
Note 1: Logical NOT (!)
Note 2: Map
Note 3: Access an array item by its index
Note 4: Strict equality (===)
Note 4: Javascript Recursion
Blog Cover Image Credit
Top comments (0)