Skip to main content

22. Climbing Stairs

easyAsked at Asana

Count the distinct ways to reach the top of an n-step staircase using 1 or 2 steps at a time — Asana uses this Fibonacci-DP warmup to assess how cleanly you reduce a novel problem to overlapping subproblems before coding.

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

Problem

You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Return the number of distinct ways you can reach the top.

Constraints

  • 1 <= n <= 45

Examples

Example 1

Input
n = 2
Output
2

Explanation: Two ways: (1 step + 1 step) or (2 steps).

Example 2

Input
n = 3
Output
3

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

Approaches

1. Recursive with memoization

ways(n) = ways(n-1) + ways(n-2). Cache results to avoid repeated computation.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();

  function ways(k) {
    if (k <= 1) return 1;
    if (memo.has(k)) return memo.get(k);
    const result = ways(k - 1) + ways(k - 2);
    memo.set(k, result);
    return result;
  }

  return ways(n);
}

Tradeoff:

2. Iterative DP with two variables (optimal)

Only the two previous steps matter. Track them in two variables — constant space, single pass.

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:

Asana-specific tips

Asana uses Climbing Stairs as a communication check, not a hard algorithm test. They want you to identify the Fibonacci recurrence yourself — don't wait to be told. Say: 'To reach step n I must have come from n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2).' Then optimize from memoization to the two-variable O(1)-space solution. Candidates who jump straight to code without the recurrence explanation typically score lower.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →