Skip to main content

70. Climbing Stairs

easyAsked at Canva

Count distinct ways to climb n steps taking 1 or 2 steps at a time — Canva uses this classic DP warmup to check whether you recognize the Fibonacci recurrence and can articulate memoization vs. bottom-up tabulation before the harder design-system problems.

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

Problem

You are climbing a staircase with n steps. Each time you can climb either 1 or 2 steps. Return the number of distinct ways to reach 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: Three ways: (1+1+1), (1+2), (2+1).

Approaches

1. Recursive with memoization (top-down DP)

Recurse on climbStairs(n-1) + climbStairs(n-2) with a cache to avoid recomputation.

Time
O(n)
Space
O(n)
function climbStairs(n) {
  const memo = new Map();
  function dp(i) {
    if (i <= 1) return 1;
    if (memo.has(i)) return memo.get(i);
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }
  return dp(n);
}

Tradeoff:

2. Optimal (bottom-up, two variables)

Recognize the Fibonacci structure and track only the last two values, reducing space to O(1).

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

Tradeoff:

Canva-specific tips

Canva uses this as a litmus test for DP fluency, not as the main interview problem. The expected path is: state the recurrence clearly (ways(n) = ways(n-1) + ways(n-2)), explain why memoization is needed over naive recursion, then immediately propose the O(1)-space Fibonacci variant. Candidates who jump to the two-variable solution without naming the recurrence first lose points — the reasoning matters more than the code at this stage.

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 Canva interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →