Skip to main content

8. Climbing Stairs

easyAsked at ByteDance

Count distinct ways to climb n stairs taking 1 or 2 steps — ByteDance uses it to test the leap from recursion to DP before deeper ranking-DP problems.

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

Problem

You are climbing a staircase with n steps and can take 1 or 2 steps at a time. 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 = 3
Output
3

Approaches

1. Naive recursion

Recursively solve for n-1 and n-2 without memoization.

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

Tradeoff:

2. Iterative two-variable DP

Track only the previous two values since the recurrence f(n) = f(n-1) + f(n-2) only depends on them.

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++) {
    [a, b] = [b, a + b];
  }
  return b;
}

Tradeoff:

ByteDance-specific tips

ByteDance interviewers want you to call out the Fibonacci structure and immediately argue for constant space, matching the disciplined memory hygiene their inference team enforces.

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

Practice these live with InterviewChamp.AI →