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

Hiring now

Data engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Data Engineer
EQS Group · Barcelona
Senior Data Engineer, Telemetry & Analytics Tooling
Interactive Brokers · Greenwich, CT, USA
Director, Data Engineering
Strive Health · Denver, CO

Or practice this question first

Next question