# The Staircase Problem

> One step or two, the choices add up.

Canonical URL: <https://datadriven.io/problems/the_staircase_problem>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a positive integer n, return the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. The answer is the (n+1)-th Fibonacci number.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **dynamic programming** recognition and implementation. The staircase problem is isomorphic to the Fibonacci sequence and is the canonical DP warm-up that probes whether a candidate can identify overlapping subproblems and avoid exponential recursion.

> **Trick to Solving**
>
> The number of ways to reach step n equals the sum of ways to reach step n-1 (take 1 step) and step n-2 (take 2 steps). This is the Fibonacci recurrence: `f(n) = f(n-1) + f(n-2)`.

---

### Break down the requirements

#### Step 1: Define base cases

`f(0) = 1` (one way to stand at the ground), `f(1) = 1` (one way to reach step 1).

#### Step 2: Build up iteratively

Use two variables to track the previous two values and iterate from 2 to n. This avoids the exponential blowup of naive recursion.

---

### The solution

**Bottom-up Fibonacci with O(1) space**

```python
def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1
    prev2 = 1
    prev1 = 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    result = prev1
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) for a single pass from 2 to n.
> 
> **Space:** O(1). Only two variables track the state, no array needed.

> **Interviewers Watch For**
>
> Starting with recursion and then optimizing to iteration shows the DP thinking process. But jumping straight to the iterative solution with clear explanation is equally strong.

> **Common Pitfall**
>
> Naive recursion without memoization gives O(2^n) time complexity. For n = 40, this takes billions of operations.

---

## Common follow-up questions

- What if you could take 1, 2, or 3 steps? _(Tests extending the recurrence to three terms: `f(n) = f(n-1) + f(n-2) + f(n-3)`.)_
- What if certain steps were blocked? _(Tests adding conditional checks inside the loop to skip forbidden positions.)_
- Can you solve this in O(log n) time? _(Tests knowledge of matrix exponentiation on the Fibonacci recurrence.)_
- What is the relationship to Fibonacci numbers? _(Tests mathematical insight: `climb_stairs(n) == fibonacci(n+1)`.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_staircase_problem)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.