Skip to main content

70. Climbing Stairs

easyAsked at HubSpot

HubSpot uses Climbing Stairs as an entry point into dynamic programming thinking — they want to see you recognize overlapping subproblems and memoize rather than recompute, a discipline that directly applies to their complex workflow-evaluation engines.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE candidates cite Climbing Stairs as a common screen-round DP introduction.
  • r/cscareerquestions (2025-09)— Mentioned in HubSpot interview prep threads as a typical easy DP warm-up.

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 = 3
Output
3

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

Example 2

Input
n = 5
Output
8

Explanation: Eight distinct ways to climb 5 stairs taking 1 or 2 steps at a time.

Approaches

1. Naive recursion

f(n) = f(n-1) + f(n-2) with base cases f(1) = 1, f(2) = 2. Intuitive but exponential due to repeated subproblem recomputation.

Time
O(2^n)
Space
O(n) call stack
function climbStairs(n) {
  if (n <= 2) return n;
  return climbStairs(n - 1) + climbStairs(n - 2);
}

Tradeoff: Good for stating the recurrence relation, but never acceptable as a final answer. Always pivot to memoization or bottom-up DP immediately after presenting this.

2. Bottom-up DP (space-optimized)

The number of ways to reach step n depends only on steps n-1 and n-2 — identical to Fibonacci. Track just two variables instead of a full DP array.

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: O(n) time, O(1) space — optimal. State the Fibonacci connection explicitly: 'This recurrence is identical to Fibonacci starting from f(1)=1, f(2)=2.' HubSpot interviewers appreciate recognizing the pattern quickly.

HubSpot-specific tips

HubSpot's interview culture values stating the pattern name before implementing it. Say: 'This is a Fibonacci sequence starting at n=1 and n=2, so I can solve it with bottom-up DP using only two variables.' They may extend the problem to 3 steps or variable step sizes — be ready to generalize the recurrence. Java/Python are equally fine; the algorithm is language-agnostic.

Common mistakes

  • Setting base cases as f(0) = 1, f(1) = 1 — while valid for Fibonacci, it's confusing here; use f(1) = 1, f(2) = 2 to match the problem domain.
  • Allocating a full dp array of size n+1 when only two variables are needed.
  • Not handling n = 1 before entering the loop — without the guard, prev1 = 2 is returned, but n = 1 should return 1.
  • Presenting only the recursive solution without pivoting to DP — HubSpot expects you to optimize.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps? Generalize the recurrence to sum the last k values.
  • Minimum Cost Climbing Stairs (LC 746) — each step has a cost; find the cheapest path.
  • What if n is very large (up to 10^18) — matrix exponentiation or fast doubling brings it to O(log n).

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

Because f(n) = f(n-1) + f(n-2): to reach step n, you either came from step n-1 (took 1 step) or step n-2 (took 2 steps). The recurrence is structurally identical.

What is f(0) in this context?

f(0) = 1 represents the one way to 'do nothing' and stay at the bottom. It's a valid base case for generalizing, but in the two-variable approach you can skip it by using f(1)=1, f(2)=2 directly.

Can n = 45 cause integer overflow in JavaScript?

No — f(45) = 1,836,311,903, which is well within JavaScript's safe integer range (2^53 - 1).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →