Skip to main content

70. Climbing Stairs

easyAsked at Elastic

Count the distinct ways to climb n stairs taking 1 or 2 steps at a time. Elastic uses this as an entry-level dynamic programming probe — if you can articulate why the recurrence is Fibonacci and spot the O(1) space optimization, you signal that you think about caching and state compression the way Elasticsearch's query cache does.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-11)— Elastic early-round phone screens include dynamic programming warm-ups; climbing stairs cited alongside coin change.
  • Blind (2025-08)— Elastic SWE thread identifies basic DP as a consistent screening filter before distributed-systems design questions.

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. Bottom-up DP with O(1) space

The number of ways to reach step i is ways(i-1) + ways(i-2) — the same Fibonacci recurrence. Use two variables instead of an array to keep space constant.

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

Tradeoff: Optimal time and space. The rolling-two-variables pattern is worth naming explicitly — it demonstrates you understand that DP tables can often be compressed to only the last few states.

2. Memoized recursion (top-down)

Recursively compute ways(n) = ways(n-1) + ways(n-2), caching results to avoid recomputation.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function dp(k) {
    if (k <= 2) return k;
    if (memo.has(k)) return memo.get(k);
    const result = dp(k - 1) + dp(k - 2);
    memo.set(k, result);
    return result;
  }
  return dp(n);
}

Tradeoff: O(n) time and O(n) space for the memo map plus O(n) call stack. Good for explaining the recurrence, but the iterative version is strictly better for n = 45.

Elastic-specific tips

Elastic interviews value the ability to recognize Fibonacci under disguise. Say explicitly: 'This is the Fibonacci sequence shifted by one — ways(n) = ways(n-1) + ways(n-2) because the last step is either a 1-step or a 2-step.' Then pivot immediately to the O(1) space optimization. If the interviewer asks about generalizing to k step sizes, describe a sliding window of k values summed at each step.

Common mistakes

  • Base case off-by-one — n=1 should return 1, n=2 should return 2; starting the loop at 3 requires both initialized correctly.
  • Allocating a full DP array of size n when two variables suffice.
  • Not recognizing the Fibonacci pattern and computing it with exponential naive recursion.
  • Returning n instead of the correct base case for n=1.

Follow-up questions

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

  • What if you could take up to k steps at a time? (Sliding-window sum of k previous states.)
  • Coin Change (LC 322) — generalization where step sizes are arbitrary coin denominations.
  • How would you count ways if certain steps are broken and unavailable?

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 this Fibonacci?

To reach step n, you either came from step n-1 (one step) or step n-2 (two steps). So ways(n) = ways(n-1) + ways(n-2), which is exactly the Fibonacci recurrence with ways(1)=1, ways(2)=2.

Why not use the closed-form Binet's formula?

For an interview, the iterative DP is cleaner and avoids floating-point precision issues that affect correctness at large n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →