Climbing Stairs (LeetCode 70)
A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.
Count how many distinct sequences of moves get you all the way from the bottom to step n.
Worked Examples
n = 22n = 33⚖️Formal Constraints & Bounds
1 <= n <= 45
Core Insight
Two rolling state variables eliminate all array allocation, achieving O(1) auxiliary memory.
Real-World Scenario & Production Applications
Staircase step counting, sequence tiling combinatorics.
Subproblems & Recurrence Decomposition3 Phases
There is 1 way to reach step 1 (a = 1) and 2 ways to reach step 2 (b = 2).
a, b = 1, 2 # 1 step: 1 way, 2 steps: 2 waysStep-by-Step Execution Trace Table
| Step n | Ways(n-2) | Ways(n-1) | Ways(n) = Sum |
|---|---|---|---|
| 1 | - | - | 1 |
| 2 | - | - | 2 |
| 3 | 1 | 2 | 3 |
| 4 | 2 | 3 | 5 |
| 5 | 3 | 5 | 8 |
| 1 | prev2, prev1 = 1, 1 |
| 2 | for _ in range(2, n + 1): |
| 3 | curr = prev1 + prev2 |
| 4 | prev2 = prev1 |
| 5 | prev1 = curr |
| 6 | return prev1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Climbing Stairs is the quintessential linear recurrence relation. The naive recursive solution branches twice at every step, creating a call tree of size filled with duplicate calculations of subproblems like climbStairs(n-3). By recognizing that the state space is a DAG(Directed Acyclic Graph) with vertices and edges, we invert the computation into a bottom-up sweep. Starting from base cases and , we compute each successive state in time.
🏟️ The Analogy: Dominoes Falling Forward
Imagine laying out a line of dominoes where the force needed to topple domino comes from the combined impact of domino and domino . You know the exact force of the first two dominoes. Rather than asking "what made domino fall?" and tracing backward through a branching tree of questions that grows exponentially, you simply push domino 1 and 2 forward. The wave of computation propagates linearly from left to right, solving each step once and for all.
🔑 Why It Works
Python's tuple unpacking a, b = b, a + b captures the recurrence transition atomically without temporary variables, evaluating the -th Fibonacci state in time and memory.
Base case index mapping: has 1 way, has 2 ways. Forgetting to handle separately when pre-allocating an array of size 2 causes
IndexError.Integer overflow in typed languages: For large (or Fibonacci variants), intermediate values exceed 32-bit signed ints; use 64-bit types or BigInt.
Over-complicating with matrix exponentiation: While matrix exponentiation exists, for simple linear rolling iteration is cleanest and runs in ms.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linear step progression where each step depends on the previous 1 or 2 steps.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after each step i, prev1 is the number of ways to reach step i and prev2 is the number of ways to reach step i - 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting prev1 = curr before prev2 = prev1, so both variables hold the same value.
Starting from 1, 2 while the loop starts at step 2, which makes every answer one step too far along.
Using recursion without memoization (O(2^N) time).
Allocating an
O(N)array when only 2 scalar variables are needed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I start with
prev2 = 1andprev1 = 1: one way to stand on step 0 and one way to reach step 1. From step 2 ton, I computecurr = prev1 + prev2, then setprev2 = prev1andprev1 = curr, in that order. I returnprev1. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = dp[i-1] + dp[i-2]. Since each state depends only on previous 2 values, rolling variables (prev1, prev2) compute answer in N additions.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 2 scalar integer registers.
T(N) = N · O(1) = O(N)
Derivation Progression
f(n) = f(n-1) + f(n-2)
Can arrive at step n from step n-1 (1 step) or step n-2 (2 steps).
a, b = b, a + b
Updates state in O(1) time per step.
N additions = O(N)
Computes exact Fibonacci sequence in linear time.
Variable Definitions
Total number of staircase steps
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar variables
O(1) Integer count
Boundary Best / Worst Cases
for N <= 2.
.
for arbitrary N.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "climb 1 or 2 steps", "distinct ways to reach the top". Canonical Fibonacci recurrence: to reach step , you must have jumped from step (1 step) or step (2 steps): .
. Time budget .
Allocating an array: senior systems engineering optimizes space to strictly via rolling variables.
Climbing Stairs (LeetCode 70)
A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.
Count how many distinct sequences of moves get you all the way from the bottom to step n.
Worked Examples
n = 22n = 33⚖️Formal Constraints & Bounds
1 <= n <= 45
Core Insight
Two rolling state variables eliminate all array allocation, achieving O(1) auxiliary memory.
Real-World Scenario & Production Applications
Staircase step counting, sequence tiling combinatorics.
Subproblems & Recurrence Decomposition3 Phases
There is 1 way to reach step 1 (a = 1) and 2 ways to reach step 2 (b = 2).
a, b = 1, 2 # 1 step: 1 way, 2 steps: 2 waysStep-by-Step Execution Trace Table
| Step n | Ways(n-2) | Ways(n-1) | Ways(n) = Sum |
|---|---|---|---|
| 1 | - | - | 1 |
| 2 | - | - | 2 |
| 3 | 1 | 2 | 3 |
| 4 | 2 | 3 | 5 |
| 5 | 3 | 5 | 8 |
| 1 | prev2, prev1 = 1, 1 |
| 2 | for _ in range(2, n + 1): |
| 3 | curr = prev1 + prev2 |
| 4 | prev2 = prev1 |
| 5 | prev1 = curr |
| 6 | return prev1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Climbing Stairs is the quintessential linear recurrence relation. The naive recursive solution branches twice at every step, creating a call tree of size filled with duplicate calculations of subproblems like climbStairs(n-3). By recognizing that the state space is a DAG(Directed Acyclic Graph) with vertices and edges, we invert the computation into a bottom-up sweep. Starting from base cases and , we compute each successive state in time.
🏟️ The Analogy: Dominoes Falling Forward
Imagine laying out a line of dominoes where the force needed to topple domino comes from the combined impact of domino and domino . You know the exact force of the first two dominoes. Rather than asking "what made domino fall?" and tracing backward through a branching tree of questions that grows exponentially, you simply push domino 1 and 2 forward. The wave of computation propagates linearly from left to right, solving each step once and for all.
🔑 Why It Works
Python's tuple unpacking a, b = b, a + b captures the recurrence transition atomically without temporary variables, evaluating the -th Fibonacci state in time and memory.
Base case index mapping: has 1 way, has 2 ways. Forgetting to handle separately when pre-allocating an array of size 2 causes
IndexError.Integer overflow in typed languages: For large (or Fibonacci variants), intermediate values exceed 32-bit signed ints; use 64-bit types or BigInt.
Over-complicating with matrix exponentiation: While matrix exponentiation exists, for simple linear rolling iteration is cleanest and runs in ms.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linear step progression where each step depends on the previous 1 or 2 steps.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after each step i, prev1 is the number of ways to reach step i and prev2 is the number of ways to reach step i - 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Setting prev1 = curr before prev2 = prev1, so both variables hold the same value.
Starting from 1, 2 while the loop starts at step 2, which makes every answer one step too far along.
Using recursion without memoization (O(2^N) time).
Allocating an
O(N)array when only 2 scalar variables are needed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I start with
prev2 = 1andprev1 = 1: one way to stand on step 0 and one way to reach step 1. From step 2 ton, I computecurr = prev1 + prev2, then setprev2 = prev1andprev1 = curr, in that order. I returnprev1. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = dp[i-1] + dp[i-2]. Since each state depends only on previous 2 values, rolling variables (prev1, prev2) compute answer in N additions.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 2 scalar integer registers.
T(N) = N · O(1) = O(N)
Derivation Progression
f(n) = f(n-1) + f(n-2)
Can arrive at step n from step n-1 (1 step) or step n-2 (2 steps).
a, b = b, a + b
Updates state in O(1) time per step.
N additions = O(N)
Computes exact Fibonacci sequence in linear time.
Variable Definitions
Total number of staircase steps
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar variables
O(1) Integer count
Boundary Best / Worst Cases
for N <= 2.
.
for arbitrary N.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "climb 1 or 2 steps", "distinct ways to reach the top". Canonical Fibonacci recurrence: to reach step , you must have jumped from step (1 step) or step (2 steps): .
. Time budget .
Allocating an array: senior systems engineering optimizes space to strictly via rolling variables.