70. Climbing Stairs
Asked at Google, Meta, Amazon, Microsoft and 4 more
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Dynamic Programming
Companies
8
Problem
You are standing at the bottom of a staircase with n steps. In one move you may go up either 1 step or 2 steps. Count how many different sequences of moves bring you exactly to the top.
Two ways are different if the order of your moves is different. For example, 1 + 2 and 2 + 1 are two separate ways, even though both add up to 3.
Return the total number of distinct ways as an integer.
Two ways to reach step 3
Constraints
- ●
1 <= n <= 45
Examples
n = 22n = 33Asked At
8 companies| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
| Adobe | Easy | View all Adobe questions → |
| Walmart | Easy | View all Walmart questions → |
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
To reach step n, you could have come from step n-1 (took 1 step) or step n-2 (took 2 steps). So ways(n) = ways(n-1) + ways(n-2).
Base cases: ways(1) = 1 (one 1-step), ways(2) = 2 (two 1-steps or one 2-step).
This is the Fibonacci sequence: 1, 2, 3, 5, 8, 13, 21... Each number is the sum of the previous two.
Space optimization: you only need the last two values. Use two variables instead of an array.
Edge cases: n=1 (1 way), n=2 (2 ways).
Optimal Approach
Step 1: Base cases — if n <= 2, return n.
Step 2: Initialize prev2 = 1 (ways(1)), prev1 = 2 (ways(2)).
Step 3: For i from 3 to n:
current = prev1 + prev2
prev2 = prev1
prev1 = current
Step 4: Return prev1.
This is iterative Fibonacci with O(1) space. Each step is the sum of the previous two, just like Fibonacci.
Time: O(n). Space: O(1).
Each answer is the sum of the two before it
What Trips People Up in Real Interviews
Not recognizing this as the Fibonacci sequence. ways(n) = ways(n-1) + ways(n-2) with base cases ways(1) = 1, ways(2) = 2.
Using recursion without memoization. That's O(2^n) and will time out. Use iterative DP or memoization.
Forgetting the base cases. ways(1) = 1, ways(2) = 2. Without these, the recurrence doesn't work.
Not handling n = 0. The problem says n >= 1, but if n = 0, return 1 (one way to stay at the top).
Using a full DP array when only two variables are needed. Each step depends on the previous two — use two variables for O(1) space instead of an O(n) array.
Solution Code
O(n) timedef climbStairs(n):
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return bFrequently Asked Questions
What is the Climbing Stairs problem?
You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top? This is the Fibonacci sequence in disguise.
How do you solve Climbing Stairs?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Climbing Stairs?
Climbing Stairs is asked at Google, Meta, Amazon, Microsoft, Apple, Adobe, Walmart, Bloomberg. It is a easy difficulty problem.
What are common mistakes on Climbing Stairs?
- Not recognizing this as the Fibonacci sequence. `ways(n)` = `ways(n-1)` + `ways(n-2)` with base cases `ways(1)` = 1, `ways(2)` = 2.
- Using recursion without memoization. That's `O(2^n)` and will time out. Use iterative DP or memoization.
- Forgetting the base cases. `ways(1)` = 1, `ways(2)` = 2. Without these, the recurrence doesn't work.
- Not handling `n = 0`. The problem says n >= 1, but if `n = 0`, return 1 (one way to stay at the top).
- Using a full DP array when only two variables are needed. Each step depends on the previous two — use two variables for `O(1)` space instead of an `O(n)` array.