Coding

LeetCode Climbing Stairs solution

0
(0)

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

I started thinking of solutioning this. First thing that came to my mind was since the steps are a permutations of either 1 step or 2 steps, can I solve this using some permutation logic. I tried for some time but gave up. I saw the hint. The hint mentioned

To reach nth step, what could have been your previous steps? (Think about the step sizes)

From the hint, I could deduce that if I am able to find relation between n-1 steps and n steps, then probably I can solve the problem. At least now I was sure that it is a recursion problem. Unfortunately I could not derive an exact relationship of climbing (n-1) steps and climbing (n) steps. At this point I thought of partially seeing the solution. From there I got much clearer hint that climbing of n steps can be found out if we know ways of climbing n-2 steps and climbing n-1 steps.

I started putting some examples

N = 1 The steps can be 1. So only 1 way to climb.

N = 2 The steps will be (1,1) (2). So two ways to climb.

For N = 3. we can add 2 to N = 1 steps. The steps will be (1,2). And then we can add 1 to N=2 steps. So the steps will be (1,1,1), (2,1). So for N = 3 the steps are sum of steps when N = 1 and when N = 2.

So the formula for finding climbing steps would be

Climb (N) = Climb(N-1) + Climb(N-2)

With this I could now solve this with recursion.

public int climbStairs1(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        return climbStairs(n-2) + climbStairs(n-1);
    }

While this will return correct result, the time complexity of this is very bad. It would be O(2^N). Then I tried doing it better using applying dynamic programming/memoization.

public int climbStairs2(int n) {
        if (dp == null) { dp = new Integer[n+1];}
        if (dp[n] != null) return dp[n];
        if (n == 0) {dp[0] = 0; return 0; }
        if (n == 1) {dp[1] = 1; return 1; }
        if (n == 2) {dp[2] = 2; return 2; }
        if (dp[n-2] == null) dp[n-2] = climbStairs(n-2);
        if (dp[n-1] == null) dp[n-1] = climbStairs(n-1);
        dp[n] = dp[n-1] + dp[n-2];
        return dp[n];
    }

This was better. Now the time complexity is reduced from O(2^N) to O(N). Is there further scope of optimization. I tried using bottom up approach since we need value of last N only.


    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int next, current, prev;
        current = 2;
        prev = 1;
        next = 0;
        for (int i=3;i<=n; i++) {
            next = current + prev;            
            prev = current;
            current = next;
        }
        return next;
    }

And this is fastest solution on LeetCode. :)

This is no way an easy problem unless you know Fibonacci series concept beforehand. So don’t get discouraged that you were not able to solve this problem despite LeetCode saying it is easy. Deriving correct recursion sub method is the key to solve these kind of problems. And once solved, you can definitely show off your tech prowess in the interviews. 🙂

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?