Skip to main content

70. Climbing Stairs

easyAsked at IBM

Climbing Stairs is IBM's intro-to-DP screener — the candidate's first chance to demonstrate they recognize Fibonacci, can derive the recurrence on the whiteboard, and can collapse the memoization to two scalar variables for O(1) space.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— Recurring IBM SWE-1 and SWE-2 phone-screen problem.
  • LeetCode (2026-Q1)— Top-30 IBM-tagged problem.
  • GeeksforGeeks (2025-11)— Cited in IBM interview-experience archive (multiple campus recruits).

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, 2

Example 2

Input
n = 3
Output
3

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

Example 3

Input
n = 5
Output
8

Approaches

1. Naive recursion (no memo)

ways(n) = ways(n-1) + ways(n-2). Base cases at n=1 and n=2.

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

Tradeoff: Cleanest recurrence statement but recomputes the same subproblems exponentially. At n=45 it's 35 billion calls — times out. Useful as the on-board derivation before you add a memo.

2. Memoized recursion

Cache subproblem results in an array indexed by n.

Time
O(n)
Space
O(n)
function climbStairsMemo(n) {
  const memo = new Array(n + 1);
  const solve = (k) => {
    if (k <= 2) return k;
    if (memo[k] !== undefined) return memo[k];
    memo[k] = solve(k - 1) + solve(k - 2);
    return memo[k];
  };
  return solve(n);
}

Tradeoff: Linear time and linear stack. Cleaner derivation path from the naive version but still O(n) call stack. Bridge step on the whiteboard before you collapse to the iterative version.

3. Two-variable rolling (optimal)

Only the last two answers are needed. Roll two scalar variables forward.

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

Tradeoff: O(1) space and the canonical answer. The collapse from O(n) memo to two scalars is the move IBM specifically grades on this problem — demonstrates you understand the data dependencies of the recurrence.

IBM-specific tips

IBM uses Climbing Stairs as the gateway to whether you recognize DP and can collapse memory. Walk the interviewer through the THREE stages — naive recursion → memo → rolling scalars — even though only the last one runs in time. Explicitly say 'each subproblem only depends on the previous two, so I can drop the array and use two variables.' That sentence is the rubric point.

Common mistakes

  • Indexing the memo array off by one (using memo[n] vs memo[n-1]).
  • Initial values wrong: ways(0) is typically taken as 1 (one way to stand still), but the LeetCode spec starts n>=1 so ways(1)=1, ways(2)=2.
  • Allocating the memo array as size n instead of n+1 — out of range at the top.
  • Forgetting to seed prev2 and prev1 with the base cases — the loop produces 0 forever.

Follow-up questions

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

  • Climbing Stairs with variable step sizes [1, 2, 3] (a generalization of Tribonacci).
  • Min Cost Climbing Stairs (LeetCode 746).
  • What if some steps are broken and you must skip them?
  • Solve in O(log n) using matrix exponentiation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is this just Fibonacci?

Yes — climbStairs(n) = fib(n+1) with the standard 1-indexed Fibonacci. IBM specifically wants you to recognize the recurrence and then optimize it. Saying 'this is Fibonacci' out loud earns the pattern-recognition rubric checkbox; then you have to actually code it cleanly.

When is the O(log n) matrix-exponentiation version expected?

Only as a follow-up for senior-loop candidates or when the interviewer explicitly bumps n. For the base problem at n<=45, the rolling-scalar O(n) is the canonical answer and matrix-exp would be overkill. Mention it exists; don't ship it unless asked.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →