EasyCoding

Climbing Stairs

Asked at

Media.net

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer n, there is a staircase with n steps, starting from the 0th step.

Determine the number of unique ways to reach the nth step, given that each move can be either 1 or 2 steps at a time.

Input: n = 2 Output: 2 Explanation: There are 2 unique ways to climb to the 2nd step:

1 step + 1 step
2 steps

Input: n = 3 Output: 3 Explanation: There are 3 unique ways to climb to the 3rd step:

1 step + 1 step + 1 step
2 steps + 1 step
1 step + 2 steps

Input: n = 1

1 <= n <= 45

cpp

class Solution {
public:
    int climbStairs(int n) {

    }
};

java

class Solution {
    public int climbStairs(int n) {

    }
}

python

class Solution:
    def climbStairs(self, n):

javascript

class Solution {
    climbStairs(n) {

    }
}

csharp

public class Solution {
    public int climbStairs(int n) {
        
    }
}

func climbStairs(n int) int {
	
}

Stuck? Show a way to structure it+

01Define ways(i) as the ways to reach step i.
02Use ways(i)=ways(i-1)+ways(i-2).
03Initialize the first two reachable states.
04Keep only the previous two values.

Reference answer

The final move to step i came from i-1 by taking one step or from i-2 by taking two, so ways(i) = ways(i-1) + ways(i-2). Start with ways(0)=1 and ways(1)=1, then iterate through n. Two variables are enough because older states are never used. This is O(n) time and O(1) space. It is Fibonacci shifted by one; avoid an exponential recursive implementation unless it is memoized. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

What changes if steps of size 1, 2, or 3 are allowed?
Tests: generalizing recurrence
How would you compute a huge n modulo M?
Tests: modular arithmetic

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question