Skip to main content

7. Climbing Stairs

easyAsked at Square

Count the distinct ways to climb n stairs taking 1 or 2 steps. Square uses this as a DP primer to see whether you spot the Fibonacci recurrence — and whether you reach for memo or iteration, signalling how you'd handle state machines in their transaction-retry logic.

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

Source citations

Public interview reports confirming this problem appears in Square loops.

  • Glassdoor (2025)— Square Reader firmware screen warm-up.
  • LeetCode Discuss (2026)— Cash App backend interns.

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: 1+1 or 2.

Example 2

Input
n = 3
Output
3

Explanation: 1+1+1, 1+2, 2+1.

Approaches

1. Naive recursion

ways(n) = ways(n-1) + ways(n-2), base cases ways(0) = ways(1) = 1.

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

Tradeoff: Exponential; recomputes the same subproblems repeatedly.

2. Iterative two-variable DP

Track previous two answers; roll forward.

Time
O(n)
Space
O(1)
function climbStairs(n) {
  if (n <= 1) return 1;
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

Tradeoff: Linear time, constant space. The Fibonacci shape is the punchline.

Square-specific tips

Square interviewers grade this on whether you recognize the Fibonacci shape and skip straight to O(1) space without scaffolding through a full array. Mention overflow at large n if asked — it shows you think about boundary behavior, the same instinct they want around payment amount precision.

Common mistakes

  • Allocating an O(n) array when two variables suffice.
  • Off-by-one base cases — ways(0) is conventionally 1 (the empty path).
  • Forgetting to handle n=1 explicitly in the iterative version.

Follow-up questions

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

  • What if you can take 1, 2, or 3 steps?
  • Variable step set {1, 3, 5}.
  • Decode Ways (LC 91) — same DP shape, harder transitions.

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 is ways(0) = 1?

There's one way to do nothing — the empty path. This convention keeps the recurrence clean.

What about matrix exponentiation?

O(log n) via 2x2 matrix power. Overkill here but worth mentioning as a flex.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →