Skip to main content

70. Climbing Stairs

easyAsked at Glean

Glean uses this to probe dynamic programming intuition — recognizing that the answer is just Fibonacci reveals whether a candidate spots optimal substructure without prompting, a skill that translates directly to ranking-function design.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2025-11)— Glean candidates report climbing stairs as an occasional DP warm-up in early phone screens.
  • Blind (2025-07)— Mentioned in Glean interview prep threads as a classic intro-DP problem that tests whether you spot the recurrence quickly.

Problem

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?

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 2
Output
2

Explanation: Two ways: (1+1) or (2).

Example 2

Input
n = 3
Output
3

Explanation: Three ways: (1+1+1), (1+2), (2+1).

Approaches

1. Dynamic programming (bottom-up, O(n) space)

Build up dp[i] = number of ways to reach step i. Base cases dp[1]=1, dp[2]=2. Recurrence: dp[i] = dp[i-1] + dp[i-2].

Time
O(n)
Space
O(n)
function climbStairs(n) {
  if (n <= 2) return n;
  const dp = new Array(n + 1);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

Tradeoff: Clear recurrence, easy to explain. O(n) space can be optimized to O(1) by keeping only the last two values.

2. Fibonacci with two variables (O(1) space)

Since dp[i] only depends on dp[i-1] and dp[i-2], use two rolling variables instead of the full array.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(1) space — the polished answer after establishing the DP recurrence. Present the full array version first to show your reasoning, then optimize.

Glean-specific tips

Say the key insight out loud before coding: 'To reach step i I could have come from step i-1 or i-2, so the count is the sum of those two — this is Fibonacci.' Glean values engineers who name the recurrence cleanly. For n ≤ 45 the O(n) solution is more than fast enough; there is no need to reach for matrix exponentiation.

Common mistakes

  • Off-by-one on base cases — dp[0] = 1 (one way to stand at the bottom doing nothing) or dp[1] = 1, dp[2] = 2 are both valid; be consistent.
  • Returning n for base cases without handling n = 1 separately — n = 1 returns 1, not 2.
  • Using recursion without memoization — O(2^n) blows up; always mention memoization or iteration.
  • Confusing the number of steps with the number of stairs — the loop runs from 3 to n inclusive.

Follow-up questions

An interviewer at Glean may pivot to one of these next:

  • What if you can take 1, 2, or 3 steps at a time? (Tribonacci variant)
  • Coin Change (LC 322) — a generalization where step sizes are arbitrary denominations.
  • What if some steps are broken and cannot be stepped on?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is dp[2] = 2 and not dp[2] = dp[1] + dp[0]?

It equals dp[1] + dp[0] = 1 + 1 = 2 if you define dp[0] = 1. Both are consistent — just be explicit about your base case definition.

Can this be solved in O(log n)?

Yes, via matrix exponentiation of the Fibonacci recurrence. It is not expected in a standard interview but good to mention as a follow-up to impress.

Practice these live with InterviewChamp.AI

Drill Climbing Stairs and other Glean interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →