Climbing Stairs
Asked at Google, Meta, Amazon, Microsoft, Apple, Adobe, Walmart
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.
Asked At
| 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 → |
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.
Visual walkthrough for n=5:
ways(1) = 1
ways(2) = 2
ways(3) = ways(2) + ways(1) = 2 + 1 = 3
ways(4) = ways(3) + ways(2) = 3 + 2 = 5
ways(5) = ways(4) + ways(3) = 5 + 3 = 8
Result: 8 ways
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Climbing Stairs?
Climbing Stairs is asked at Google, Meta, Amazon, Microsoft, Apple, Adobe, Walmart. 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.