Skip to main content

23. Climbing Stairs

easyAsked at Apple

Count distinct ways to reach step n taking 1 or 2 steps at a time — Apple uses this DP gateway problem to test whether you recognize Fibonacci recurrences, a pattern behind animation frame interpolation in Core Animation.

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

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
  • Answer fits in a 32-bit signed integer
  • Distinct orderings of steps count as different ways

Examples

Example 1

Input
n = 2
Output
2

Explanation: Two ways: (1,1) or (2)

Example 2

Input
n = 4
Output
5

Explanation: Five ways: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)

Approaches

1. Recursive (naive)

Recurse with f(n) = f(n-1) + f(n-2). Exponential due to repeated subproblems.

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

Tradeoff:

2. DP (space-optimized)

Recognize the Fibonacci recurrence. Track only the last two values — no memoization array needed.

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

Tradeoff:

Apple-specific tips

Apple interviewers expect you to name the Fibonacci pattern unprompted — saying 'this is just Fibonacci with different base cases' signals pattern recognition they value. Connect it to Core Animation: interpolating keyframe counts between two anchors follows the same recurrence. They may follow up asking for the closed-form (Binet's formula) — knowing it exists but noting floating-point imprecision at large n shows depth without over-engineering.

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

Practice these live with InterviewChamp.AI →