Climbing Stairs - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

function visMainFunction(n) {
    if (n <= 2) {
        const reason = n === 1 
            ? `there is only <b>1 way</b>: take a <b>single 1-step</b>.`
            : `there are exactly <b>2 ways</b>:<br/>• <b>1 + 1</b> (two 1-steps)<br/>• <b>2</b> (one 2-step)`;

        notification(`✅ Since <b>n = ${n}</b>, ${reason}`);
        return n;
    }

    startBatch();
    let prevWays = 1, currentWays = 2;
    makeVisVariable(prevWays).options({ label: 'prevWays' }).createVis(true);
    makeVisVariable(currentWays).options({ label: 'currentWays' }).createVis(true);
    endBatch();

    explanationNotification();

    notification(`
        Let <code>Ways(i)</code> denote the number of ways to reach step <b>i</b>:  
        <code>Ways(n) = Ways(n − 1) + Ways(n − 2)</code> (Fibonacci pattern). <br/><br/>
        
        📌 We’ve already set up the <b>base cases</b>:<br/>
        • <b>prevWays</b> = <code>${prevWays}</code> → number of ways to reach step <b>1</b> = <b>1</b>.<br/>
        • <b>currentWays</b> = <code>${currentWays}</code> → number of ways to reach step <b>2</b> = <b>2</b>.<br/><br/>
        From here, for every step <b>i ≥ 3</b>, we compute number of ways to reach <b>step i</b> and will update the <code>prevWays</code> and <code>currentWays</code>.
    `);

    for (let i = 3; i <= n; i++) {
        startPartialBatch();
        notification(`
          🔄 <b>Calculating the number of ways to reach Step ${i}</b><br/>
          We can arrive here from <b>step ${i - 1}</b> (then take 1 step) or from <b>step ${i - 2}</b> (then take 2 steps).<br/>
          <code>Ways(${i}) = Ways(${i - 1}) + Ways(${i - 2})</code><br/>
          Using the running values:<br/>
          • <span style="color:#1e88e5"><b>Ways(${i - 1}) = currentWays = ${currentWays}</b></span><br/>
          • <span style="color:#f57c00"><b>Ways(${i - 2}) = prevWays = ${prevWays}</b></span><br/>
          → <b>${currentWays} + ${prevWays} = ${currentWays + prevWays}</b>.<br/><br/>
          After this iteration:<br/>
          • <b>currentWays</b> will represent the number of ways to reach Step ${i} (just computed, <b>Ways(${i}) = ${currentWays + prevWays}</b>).<br/>
          • <b>prevWays</b> will represent the number of ways to reach Step ${i - 1} (the previous <b>currentWays</b>, <b>Ways(${i - 1}) = ${currentWays}</b>).<br/>
          👉 Therefore, we reassign them so that at the end of each iteration they still correctly represent 
<b>Ways(i − 1)</b> and <b>Ways(i)</b>, where <b>i</b> is the step index whose number of ways was just calculated.
        `);
        
        let nextWays = currentWays + prevWays;
        prevWays = currentWays;
        currentWays = nextWays;

        endBatch();
    }

    notification(`
        🏁 <b>Finished!</b><br/>
        Total distinct ways to reach step <b>${n}</b> = <b>${currentWays}</b>.<br/>
        📌 This value is held in <b>currentWays</b> because, by our reassignment rule,
        it always represents <b>Ways(i)</b> for the most recent step <b>i</b> —
        and after the loop ends, that final step is <b>n</b>.
    `);
    return currentWays;
}

Approach

Problem

Count the number of distinct ways to reach step n when each move can be either 1 step or 2 steps.

Base Cases

n = 1 → exactly 1 way: take a single 1-step.
n = 2 → exactly 2 ways: 1 + 1 (two 1-steps) or 2 (one 2-step).

Key Insight (Recurrence)

Let Ways(i) denote the number of ways to reach step i. To reach step i, you must come either from step i − 1 (taking 1 step) or from step i − 2 (taking 2 steps):
Ways(i) = Ways(i − 1) + Ways(i − 2) (Fibonacci pattern).

Iterative DP with Rolling State

We avoid building an entire DP array because only the two most recent values are required. We initialize with the base cases:

prevWays = 1 → represents Ways(1).
currentWays = 2 → represents Ways(2).

For each step i from 3 to n:

At the start of iteration i:
- currentWays holds Ways(i − 1) (the number of ways to reach step i − 1).
- prevWays holds Ways(i − 2) (the number of ways to reach step i − 2).
We then compute nextWays = currentWays + prevWays, which represents the number of ways to reach step i (Ways(i)).
After this calculation, we roll the state forward:
- currentWays ← Ways(i) (just computed as nextWays).
- prevWays ← Ways(i − 1) (the old currentWays).

👉 This reassignment ensures that at the end of each iteration, the variables still correctly represent Ways(i − 1) and Ways(i), where i is the latest step index processed.

Termination & Output

The loop runs for i = 3 … n. When it finishes, the most recent step is n, so currentWays = Ways(n). 📌 The final answer is in currentWays because, by construction, it always tracks the number of ways to reach the latest step.

Time Complexity

The algorithm iterates once through the steps from 3 to n, performing only constant-time operations (addition and variable reassignment) at each iteration. Therefore, the time complexity is:

O(n) — linear in the input size n.

Space Complexity

The algorithm only maintains two variables — prevWays and currentWays — instead of storing all values in a DP array. Therefore, the space complexity is:

O(1) — constant extra space, independent of the input size n.

Input-1

Climbing Stairs - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Problem

Base Cases

Key Insight (Recurrence)

Iterative DP with Rolling State

Termination & Output

Time Complexity

Space Complexity