Practice Climbing Stairs
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
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?
Source: Climbing Stairs on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 2
2
# Example 2
n = 3
3
Constraints
How to solve Climbing Stairs
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
The final move onto step n is either a single step from n - 1 or a double step from n - 2, so the number of ways to reach n is the sum of the ways to reach those two steps. That is the Fibonacci recurrence.
Why brute force is not enough
Plain recursion that branches on taking 1 or 2 steps recomputes the same subproblems over and over. Its call count grows like 1.6^n, and with n up to 45 that exceeds a billion calls.
Approach
- Define the state as the number of distinct ways to stand on step i.
- Fix the base cases: one way to reach step 1, and two ways to reach step 2 (two singles or one double).
- Iterate from step 3 up to n, keeping only the previous two counts and setting the new count to their sum. Invariant: the two stored values are always the counts for steps i - 1 and i - 2.
- Return the count for step n.
- Mention that matrix exponentiation or the closed-form Fibonacci formula gives O(log n), but the linear loop is what is expected here.
Walkthrough of Example 2
n = 3 → 3
- Ways to reach step 1: 1 (a single step).
- Ways to reach step 2: 2 (1 + 1, or a single 2).
- Ways to reach step 3: ways(2) + ways(1) = 2 + 1 = 3.
- Return 3; the sequences are 1 + 1 + 1, 1 + 2, and 2 + 1.
Time and space
Time O(n) · Space O(1). n is the number of steps; the loop runs n times and only two counters are stored.
Interview pitfalls
- Mixing base-case conventions: if you start from step 0 it has one way (the empty climb), while step 1 has one and step 2 has two; blending conventions shifts the whole sequence by one.
- Allocating a memo array sized for n and indexing position 2 when n is 1, which goes out of bounds.
- Treating 1 + 2 and 2 + 1 as the same way; order matters here, which is why the answer is Fibonacci and not a combination count.
- Assuming 32-bit integers are always enough; the value for n = 45 is about 1.8 * 10^9, so loosening the constraint slightly requires 64-bit.
- Writing the exponential recursion and not noticing it stalls until the interviewer asks about n = 40.
Follow-up questions interviewers ask
- Allow steps of 1, 2, or 3, or any given set of step sizes; how does the recurrence generalize?
- Each step has a cost and you pay for every step you land on; find the cheapest way to the top.
- Compute the answer for n around 10^18 modulo a prime using fast matrix exponentiation.
Further reading on the technique: Fibonacci sequence
Related LeetCode Problems
Practice more problems similar to Climbing Stairs.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.