Skip to main content

6. Climbing Stairs

easyAsked at Klarna

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

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

Problem

You are climbing a staircase that takes n steps to reach the top. Each time you can either climb 1 or 2 steps. Return the number of distinct ways you can 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. Brute force

Recurse on n-1 and n-2.

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

Tradeoff:

2. Bottom-up DP

Rolling Fibonacci with two variables. Each step's count is the sum of the prior two steps.

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

Tradeoff:

Klarna-specific tips

Klarna interviewers use this warm-up to gauge whether you can compress recursion into O(1) space the same way they fold BNPL installment-counting recurrences into rolling state.

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

Practice these live with InterviewChamp.AI →