Skip to main content

11. Climbing Stairs

easyAsked at Figma

Count the number of distinct ways to climb a staircase taking 1 or 2 steps at a time. A warm-up at Figma to gauge whether you spot the Fibonacci recurrence before brute-forcing it.

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

Problem

You are climbing a staircase with n steps. Each time you can take 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

Example 2

Input
n = 4
Output
5

Approaches

1. Brute force recursion

Recurse on (n-1) and (n-2); recompute the same subproblems exponentially.

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

Tradeoff:

2. Bottom-up DP with O(1) space

Only the last two values matter, so roll two variables instead of an array. This is the Fibonacci recurrence in disguise.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

Tradeoff:

Figma-specific tips

Figma uses this as a tempo-setter — name the recurrence and the O(1) space optimization within five minutes, then they pivot you to a real canvas problem.

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

Practice these live with InterviewChamp.AI →