Skip to main content

70. Climbing Stairs

easyAsked at eBay

eBay uses Climbing Stairs as a gentle DP entry point — it tests whether you can identify overlapping subproblems and avoid recomputation. Think of it as the number of ways to paginate through a search result: each page can advance 1 or 2 results at a time. Recognizing this as Fibonacci unlocks the O(1) space optimization that senior eBay engineers expect.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— eBay candidates mention Climbing Stairs as a classic DP warm-up in phone screens for junior and mid-level roles.
  • Blind (2025-08)— eBay SWE prep threads confirm this problem as a common entry to the DP section of their interview loop.

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: Two ways: (1,1) or (2).

Example 2

Input
n = 3
Output
3

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

Approaches

1. Memoization (top-down DP)

Recursively compute ways(n) = ways(n−1) + ways(n−2) with a memo map to avoid recomputation.

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

Tradeoff: Intuitive recursive structure. O(n) space for memo + call stack. Good as the starting point; then optimize to O(1) space.

2. Iterative Fibonacci (O(1) space)

Recognize that ways(n) = ways(n−1) + ways(n−2) is the Fibonacci recurrence. Use two variables to compute iteratively.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1; // ways to reach step 1
  let prev1 = 2; // ways to reach step 2
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(1) space — optimal. This is what eBay expects you to land on after starting with the recursive approach. Name the pattern: 'This is Fibonacci starting from (1, 2).'

eBay-specific tips

State the DP recurrence before writing any code: 'To reach step n, I either came from step n−1 or step n−2 — so ways(n) = ways(n−1) + ways(n−2).' eBay interviewers reward candidates who name the pattern (Fibonacci) and immediately offer the O(1) space optimization. For n ≤ 45, even a naive recursive solution fits in time, but demonstrate that you know the efficient path.

Common mistakes

  • Off-by-one on base cases: ways(1) = 1, ways(2) = 2 — not ways(0) = 1 unless you're using a 0-indexed DP array.
  • Using a full DP array of size n+1 when only two previous values are needed — wastes O(n) space unnecessarily.
  • Exponential recursion without memoization — O(2^n) blows up for n near 45.
  • Forgetting that ways(n) is Fibonacci shifted by one — don't derive the recurrence from scratch when you can name it.

Follow-up questions

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

  • What if you could climb 1, 2, or 3 steps at a time? Generalize the recurrence.
  • Coin Change (LC 322) — a generalization where step sizes are arbitrary denominations.
  • How would you compute the answer for very large n (say 10^18)? Matrix exponentiation gives O(log n).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does ways(2) = 2 and not 1?

There are two ways to reach step 2: take two 1-steps, or take one 2-step. The recurrence counts distinct ordered sequences, not just totals.

Is this exactly Fibonacci?

Yes, but shifted: climbStairs(n) = Fib(n+1) under the standard Fibonacci definition (Fib(1)=1, Fib(2)=1). It's easier to define base cases directly for this problem.

What is the maximum value for n = 45?

climbStairs(45) = 1,836,311,903, which fits in a 32-bit signed integer. No BigInt needed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →