Skip to main content

70. Climbing Stairs

easyAsked at Gusto

Count the number of distinct ways to reach the top of an n-step staircase taking 1 or 2 steps at a time. Gusto uses this to introduce dynamic programming — they want to see you recognise the Fibonacci recurrence and optimise from O(n) space to O(1).

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-09)— Mentioned in Gusto entry-level SWE interview reports as an introductory DP problem.
  • Blind (2025-11)— Gusto threads cite Climbing Stairs as a soft DP warm-up before harder problems in the same session.

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. DP with O(n) space (tabulation)

Build a dp array where dp[i] = ways to reach step i. dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[1]=1, dp[2]=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 and easy to verify. Good starting point — then optimise space once the recurrence is established.

2. DP with O(1) space (rolling variables)

You only need the previous two values to compute the current one. Use two variables and advance them.

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 in both time and space. This is the answer Gusto expects you to land on after starting with the array version. Name the variables meaningfully — prev1/prev2 is clearer than a/b.

Gusto-specific tips

Start with the recurrence relation: 'To reach step i, I came from i-1 or i-2. So ways(i) = ways(i-1) + ways(i-2).' State the Fibonacci observation explicitly — interviewers appreciate candidates who name it. Then build the array version first and refactor to the two-variable version, narrating the space optimisation as you go.

Common mistakes

  • Off-by-one in the base case — n=1 has 1 way, n=2 has 2 ways. Mixing these up breaks all subsequent values.
  • Starting the loop from i=2 instead of i=3 when using the two-variable approach — overwrites a base case.
  • Returning the wrong variable at the end — after the loop, prev1 holds the answer, not prev2.
  • Trying to use recursion without memoisation — leads to exponential time and likely TLE or stack overflow for large n.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps at a time?
  • What if each step has a cost and you want the minimum total cost? (LC 746 — Min Cost Climbing Stairs.)
  • How would you test your solution for n = 1, n = 45, and a mid-range value?

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 equivalent to Fibonacci?

The recurrence ways(n) = ways(n-1) + ways(n-2) with ways(1)=1, ways(2)=2 is the Fibonacci sequence shifted by one. ways(n) = Fib(n+1).

Can you solve this in O(log n) time?

Yes, using matrix exponentiation of the Fibonacci recurrence. Rarely expected in interviews but a valid follow-up to mention.

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

Floating-point precision errors make it unreliable for large n in most languages. Stick with the iterative integer approach.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →