Climbing Stairs | Leetcode #70 | Easy

In this post I will discuss the solution to the leetcode problem — Climbing Stairs.

Problem:

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:

This is one of the classic interview problems I have been asked at least 2–3 times so far. Let’s take a small example before diving into the algorithm.

Let’s say the input is 3 i.e. you have to climb total 3 steps. There are 3 ways you can do that.

1. take 1 step at a time
2. take 1 step and then take 2 steps
3. take 2 steps and then take 1 step

Let’s say the input is 2 i.e. you have to climb total 2 steps. There are 2 ways you can do that.

1. take 1 step at a time
2. take 2 steps in one go

Let’s say the input is 1 i.e. you have to climb 1 step. There is only 1 way you can do that.

1. take 1 step

Do you see any pattern in the example above? The number of ways you can climb n steps is actually the sum of number of ways you can climb n -1 steps and number of ways you can climb n-2 steps. That is our algorithm to solve this problem. Let’s see how it looks —

1. Create an array steps with size = n to hold the number of ways you can travel each step in the array.
2. As a base case, if n ≤ 2 we return n for obvious reasons.
3. Initialize steps[0] = 1 and steps[1] = 2 as we saw in the example above.
4. We start from the third step until we reach n and calculate the number of ways for each step
5. In the end we return steps[n — 1] as the final output.

class Solution {
  public int climbStairs(int n) {
    int[] steps = new int[n];
    if (n <= 2) {
      return n;
    }
    steps[0] = 1;
    steps[1] = 2;
    for (int i = 2; i < n; i++) {
      steps[i] = steps[i - 1] + steps[i - 2];
    }
    return steps[n - 1];
  }
}

I hope you enjoyed solving this problem and the solution helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems