Skip to main content

70. Climbing Stairs

easyAsked at Goldman Sachs

You can climb 1 or 2 stairs at a time; how many ways to reach the top of n stairs? Goldman Sachs uses Climbing Stairs as a DP warm-up — they're grading whether you recognize the Fibonacci recurrence and the O(1) space trick.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE phone-screen reports list Climbing Stairs as a 'recognize the Fibonacci structure' question.
  • LeetCode Discuss (2025-10)— Climbing Stairs is in the top-15 of LeetCode's Goldman Sachs company tag.

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: 1+1 or 2.

Example 2

Input
n = 3
Output
3

Explanation: 1+1+1, 1+2, 2+1.

Approaches

1. Naive recursion (exponential)

f(n) = f(n-1) + f(n-2). Recurse directly.

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

Tradeoff: Times out for n > 35. Mention it to derive the recurrence, then memoize or convert to bottom-up.

2. Bottom-up DP with array

Fill dp[1..n] iteratively from dp[i] = dp[i-1] + dp[i-2].

Time
O(n)
Space
O(n)
function climbStairsDP(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: Linear time at linear extra space. The clean intermediate step to show on the whiteboard before optimizing space.

3. Two-variable rolling (optimal)

Only the last two values matter — roll forward with two scalars.

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 cur = prev1 + prev2;
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Tradeoff: Constant extra memory. This is the version Goldman wants — it demonstrates you noticed that only the last two values are referenced.

Goldman Sachs-specific tips

Goldman Sachs interviewers grade Climbing Stairs on the progression: naive recursion → memo → bottom-up → rolling-variable. Show all four mentally even if you only code the last. Naming 'Fibonacci' before writing code earns the easy point — interviewers love hearing it because it tells them you see the underlying structure, not just the surface problem.

Common mistakes

  • Memoizing the recursion but forgetting to return the cached value (always recomputes).
  • Off-by-one on dp indices — is dp[0] = 1 (empty path) or undefined? Both are defensible; just commit.
  • Allocating dp[n+1] when only dp[2] would do (works but signals you didn't see the optimization).

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • What if steps can be 1, 2, OR 3? (dp[i] = dp[i-1] + dp[i-2] + dp[i-3], same template.)
  • What if each step has a cost and you want minimum cost to reach the top? (Min Cost Climbing Stairs, LC #746.)
  • Closed-form via Binet's formula — when would you use it? (For HUGE n where matrix exponentiation in O(log n) wins.)

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 the answer Fibonacci?

Because to reach step n you came from either step n-1 (took 1 step) or step n-2 (took 2 steps). Number of ways = ways(n-1) + ways(n-2). That's Fibonacci with f(1) = 1 and f(2) = 2 — a shifted variant of the standard Fibonacci sequence.

Why is n capped at 45?

Because Fib(45) = 1836311903, just under 2^31. The cap keeps the answer within 32-bit int. For larger n you'd need BigInt or modular arithmetic.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →