Topic: Learning notes

LeetCode 70: Climbing stairs from repeated recursion to two rolling states

My Climbing Stairs path from a factorial dead end and exponential recursion to an O(n)-time, O(1)-extra-space rolling-state solution.

This problem first looked like a counting-permutations exercise. I started with factorials, then ran into two separate issues: steps of the same size are not distinct objects, and a valid route may use any possible number of two-step moves.

My next attempt found the right recurrence but timed out as n grew. The execution strategy was the problem: recursion kept recalculating the same answers. After a step-by-step AI explanation and a complete example, I rewrote the solution to keep only the previous two results. This article preserves all three stages. Publishing it does not mean I can reproduce the solution independently yet.

The problem

LeetCode 70: Climbing Stairs gives a staircase with n steps. Each move climbs either one or two steps. The task is to count the distinct sequences of moves that reach step n.

For n = 3, the routes are 1 + 1 + 1, 1 + 2, and 2 + 1, so the answer is 3. The constraint is 1 <= n <= 45.

My first direction: count permutations with factorials

This is the version I wrote before understanding the recurrence. I kept the approach intact and added TypeScript types.

function climbStairsFactorialAttempt(n: number): number {
    const isEven = n % 2 === 0;
    const howManyTwo = Math.floor(n / 2);

    function factorial(value: number): number {
        if (value < 0) return -1;

        let result = 1;
        for (let i = 1; i <= value; i++) {
            result *= i;
        }
        return result;
    }

    return factorial(howManyTwo * 2 + isEven ? 0 : 1);
}

TypeScript first rejects this expression because it adds a number and a boolean. In JavaScript, it also has a precedence problem: the conditional operator ?: has lower precedence than addition, so the argument is parsed approximately as:

factorial((howManyTwo * 2 + isEven) ? 0 : 1);

Whenever that condition coerces to true, the function calls factorial(0). Adding types alone cannot repair this version because the counting method is incomplete too.

Adding parentheses would not make a single factorial the answer. For n = 4, the valid routes are:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

The list contains different possible counts of two-step moves and repeated one-step moves. A combinatorial solution must count each possible number of two-step moves separately and add those counts. That route works, but the problem’s recurrence is easier to derive and implement correctly.

My second attempt: correct relation, repeated work

I then found the recurrence:

function climbStairsRecursive(n: number): number {
    return ways(n);
}

function ways(n: number): number {
    return n <= 2 ? n : ways(n - 1) + ways(n - 2);
}

This produces the right values. The final move into step n has exactly two possibilities:

• Move one step from n − 1.
• Move two steps from n − 2.

The groups cannot overlap because their final moves differ, and together they cover every route. Therefore:

ways(n) = ways(n - 1) + ways(n - 2)

The execution strategy is the problem. While calculating ways(5), different branches calculate ways(3) again. The number of repeated calls grows quickly with n. This version has an O(2ⁿ) upper bound and an O(n) recursion stack, making it unsuitable for n = 45.

The version I rewrote after a full walkthrough

The recurrence only depends on the previous two steps, so it does not need an entire table. This is the code I wrote after understanding the rolling-state explanation:

function climbStairs(n: number): number {
    if (n <= 2) return n;

    let prev1 = 2;
    let prev2 = 1;
    let curr = 0;

    for (let i = 3; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return curr;
}

At the start of the iteration for step i:

• prev1 is the number of routes to step i − 1.
• prev2 is the number of routes to step i − 2.

The code first calculates curr from both old values, then shifts the states forward. Reversing that order would overwrite prev1 before the current answer had used its old value.

Returning curr is safe here because n values up to 2 return early. Returning prev1 is another option if the return value should directly mean “the latest completed state.” For n at least 3, both variables hold the same answer when the loop finishes.

Tracing n = 5

The initial state stores the route counts for steps 1 and 2:

After each iteration, prev2 takes the old prev1, and prev1 takes the new curr. The next iteration still has exactly the two earlier answers it needs.

Another valid route: memoization

The recursive version could instead cache each ways(n) in an array or Map. Memoization reduces the runtime to O(n), but it still uses O(n) cache space and an O(n) call stack.

This problem only needs the preceding two states, so rolling state uses less space. Memoization is a useful intermediate step for confirming the overlapping-subproblem diagnosis; rolling state is the final approach used here.

Correctness invariant

At the start of the iteration for step i, prev1 and prev2 hold the route counts for steps i − 1 and i − 2.

Every route to step i belongs to exactly one of two groups based on its final move. The one-step group contains prev1 routes, and the two-step group contains prev2 routes. The groups are disjoint and exhaustive, so curr = prev1 + prev2 is correct.

After the state shift, prev1 holds the answer for step i and prev2 holds the answer for step i − 1. The invariant is ready for the next iteration. When the loop reaches n, the stored current result is the answer for step n.

Complexity

The loop runs from 3 through n, doing a fixed amount of work each time. Runtime is O(n). The function keeps only prev1, prev2, and curr, so extra space is O(1).

The recursive version is shorter but repeats work. Big O measures how the work grows with the input, not how many lines the implementation contains.

Executable checks

My original examples contained n = 4 and n = 30 twice. Repeating the same input does not expand coverage, and written Output/Expected blocks do not execute. These assertions cover the base cases, the first loop iteration, and the largest input:

import assert from "node:assert/strict";

assert.equal(climbStairs(1), 1);
assert.equal(climbStairs(2), 2);
assert.equal(climbStairs(3), 3);
assert.equal(climbStairs(4), 5);
assert.equal(climbStairs(5), 8);
assert.equal(climbStairs(30), 1346269);
assert.equal(climbStairs(45), 1836311903);

I ran this implementation for n = 1 through 10, n = 30, and n = 45. Finite checks do not replace the invariant, but they catch common mistakes in the initial values, loop bounds, and update order.

Common mistakes

• Treating all steps as distinct objects in one factorial calculation.
• Writing the correct recurrence without removing overlapping work.
• Updating prev1 too early and mixing state from two iterations.
• Testing only n = 4 or larger values while missing n = 1, n = 2, and the first loop iteration.
• Claiming O(1) space for recursion while ignoring the call stack.

What I learned

The useful lesson is not merely that Climbing Stairs follows the Fibonacci sequence. The recurrence has a reason: splitting all routes by the final move creates two disjoint groups, one from the previous step and one from two steps back.

A recurrence describes a relationship between states; it does not require a recursive implementation. When the current state depends on only two earlier results, a repeated call tree can become two variables. I received a full AI walkthrough for this transition, so my next review is to reproduce the invariant, code, and assertions without looking at this article.

References

• LeetCode 70: Climbing Stairs: official problem statement, examples, and constraints.
• MDN: Operator precedence: parsing order for the conditional expression in my first attempt.
• Node.js assert: executable assertions.