Skip to content

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.

Easy#70
LeetCode Problem

Climbing Stairs

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

Input
n = 2
Output
2

# Example 2

Input
n = 3
Output
3

Constraints

1 <= n <= 45

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

  1. Define the state as the number of distinct ways to stand on step i.
  2. Fix the base cases: one way to reach step 1, and two ways to reach step 2 (two singles or one double).
  3. 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.
  4. Return the count for step n.
  5. 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

  1. Ways to reach step 1: 1 (a single step).
  2. Ways to reach step 2: 2 (1 + 1, or a single 2).
  3. Ways to reach step 3: ways(2) + ways(1) = 2 + 1 = 3.
  4. 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.