Skip to main content

11. Climbing Stairs

easyAsked at Snap

Count distinct ways to climb n stairs taking 1 or 2 steps at a time. Snap uses this as a 'do you spot Fibonacci' check before harder DP.

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

Source citations

Public interview reports confirming this problem appears in Snap loops.

  • Glassdoor (2026-Q1)— Listed as a Snap warm-up to gauge DP intuition.
  • LeetCode Discuss (2025)— Frequently bundled with Fibonacci in Snap intern screens.

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

Approaches

1. Naive recursion

f(n) = f(n-1) + f(n-2) with no memoization.

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

Tradeoff: Exponential and re-computes the same subproblems. Use only to motivate memoization.

2. Bottom-up two-variable DP (optimal)

Maintain (prev2, prev1) representing f(i-2), f(i-1). Each step compute curr = prev2 + prev1, then shift.

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

Tradeoff: Linear time, constant space. Mirrors Fibonacci exactly — name that out loud.

Snap-specific tips

At Snap, identify the Fibonacci recurrence before coding. Bonus signal: when asked about following up with arbitrary steps, mention coin-change DP — Snap interviewers like to escalate this into a 'count ways under constraint' problem.

Common mistakes

  • Allocating an O(n) DP array when two variables suffice.
  • Off-by-one on base cases — confirm f(1)=1 and f(2)=2.
  • Mutating prev1 before reading it in the next step.

Follow-up questions

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

  • Steps of size 1, 2, or 3.
  • Steps from an arbitrary set (coin-change variant).
  • Min-cost climbing stairs (LC 746).

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 at step i you either came from step i-1 (one step) or step i-2 (two steps), so f(i) = f(i-1) + f(i-2).

Is the matrix-power O(log n) solution worth mentioning?

Yes for bonus — but only after you've delivered the O(n) baseline. Snap usually doesn't require it unless n becomes astronomical.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →