Skip to main content

28. Climbing Stairs

easyAsked at Postman

Count distinct ways to climb n stairs taking 1 or 2 steps at a time.

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

Problem

You are climbing a staircase of n steps. 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

Example 2

Input
n = 3
Output
3

Approaches

1. Naive recursion

ways(n) = ways(n-1) + ways(n-2). Exponential without memoization.

Time
O(2^n)
Space
O(n)
function ways(n) { return n <= 2 ? n : ways(n-1) + ways(n-2); }

Tradeoff:

2. Rolling pair

Track only the last two Fibonacci-style values; O(1) memory.

Time
O(n)
Space
O(1)
function climb(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:

Postman-specific tips

Postman expects you to spot the Fibonacci structure and collapse memory to two scalars — they value memory-tight solutions because their browser extension runs in tight memory budgets.

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

Practice these live with InterviewChamp.AI →