DSA-126 · FOCUSED PRACTICE

Climbing Stairs

Foundational · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 104 deterministic checks. Learner drafts are not executed.

Understand the problem

A staircase has n steps. Starting on the ground, move upward by exactly one or two steps at a time. Return the number of distinct ordered move sequences that land exactly on step n.

n is an int from 0 through 91, inclusive. The method checks the full bound and throws IllegalArgumentException outside it; 92 is rejected rather than returning an overflowed count.
Return an exact Java long. Different move orders count separately: [1,2] and [2,1] are different ways to reach step 3. Overshooting the target is not a way.
For n=0 return 1: the empty move sequence is one valid way to stay on the ground. The reference has no mutable caller input or shared persistent cache. The recursive baseline obeys the same value contract but is practical only for small n.

Examples

Input: n=0
Output: 1
The empty path is a complete path; returning zero would erase a necessary counting identity.
Input: n=3
Output: 3
The ordered paths are [1,1,1], [1,2], and [2,1].
Input: n=5
Output: 8
A final one-step can extend any of five paths to 4; a final two-step can extend any of three paths to 3.
Input: n=91
Output: 7540113804746346429
This is F(92), the largest supported staircase count that fits a signed long. F(93), needed for n=92, does not fit.

Before you start

Distinguishing ordered sequences from unordered combinations
A state sentence, induction, and the Java long range

Recognize the structure

The final move partitions all paths into two disjoint families. Once that final move is removed, only the remaining height matters; earlier order history does not change future options. Repeated heights make recursion expensive, and every height depends only on its two immediate predecessors. This supports a bottom-up evaluation and then a constant-space frontier. The important step is defining what is counted before writing the familiar Fibonacci-shaped recurrence.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 111/20,000 characters

Self-review

I can explain why the empty path contributes one and why final-move families are disjoint.I can derive the full table before removing it and state both rolling register meanings.I can justify the 91 limit, the temporary variable, and the difference between arithmetic counts and bit complexity.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Group all valid sequences by their last move. Which smaller heights remain?

Hint 2

Give the empty sequence a count and write a state sentence before the recurrence.

Hint 3

Keep W(s−2) and W(s−1); compute their sum before moving the two-register frontier.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate the final move recursively

Let enumerate(r) count sequences summing to r. Return one for r=0 or r=1; otherwise recursively count r−1 and r−2 and add. For n=5, both the n=4 and n=3 branches request n=2, and many more repeated requests follow. Every branch decreases a nonnegative remaining height, so the recursion terminates, but it performs exponential repeated work. A safe upper bound is O(2^n) time with O(n+1) live stack space. The implementation validates n once, then uses a private recursive helper; it does not revalidate at each call. Verification runs the baseline only through 22, while an independent exact combinatorial oracle checks every supported n through 91. No claim is made that the baseline is usable at the upper bound.

Improve the baseline

State and empty-path identity

Write W(s): the number of ordered paths from ground to exactly step s using moves 1 or 2. W(0)=1 and W(1)=1. The zero base is not a physical move; it is the single empty prefix that can be extended. This differs from asking for a nonempty sequence or counting ways to overshoot the top.

Partition by the final move

For s≥2, paths ending in 1 correspond bijectively to W(s−1), and paths ending in 2 correspond bijectively to W(s−2). The final move is different, so these families never overlap. Therefore W(s)=W(s−1)+W(s−2). Addition counts alternatives; choosing min or max would answer an optimization question instead.

Evaluate the dependency DAG in increasing height

Conceptually build the table W(0), W(1), …, W(n). Every predecessor is final before a later state reads it. For n=5 the table is [1,1,2,3,5,8]. A top-down memoized method would evaluate the same states but still retain a cache and recursive call stack.

Compress after the recurrence is clear

Before iteration s, previousTwo=W(s−2) and previousOne=W(s−1). Compute next from both old values before shifting either register. Assign previousTwo=previousOne, then previousOne=next. The conceptual table in the walkthrough is a teaching history; the Java reference stores only these registers.

Choose a numerical policy

Java int already fails at n=46; Java long works through n=91. This implementation enforces that exact range. Floating-point formulas can round and are unnecessary. Supporting arbitrary n requires BigInteger and a bit-complexity discussion, rather than silently widening a few local variables and claiming unrestricted exact arithmetic.

Why it is correct

Base cases

For zero height exactly one sequence has sum zero: empty. For height one the only sequence is [1]. The early return establishes both bases without entering the loop.

Inductive counting step

Assume both predecessor counts are exact. Removing the last move maps every path to s into exactly one path to s−1 or s−2. Appending the corresponding final move reverses the map, proving soundness and completeness. Disjoint final-move families justify addition without double counting.

Rolling invariant and termination

At entry to iteration s, the two registers equal W(s−2), W(s−1). Computing next and shifting preserves that statement for iteration s+1. The finite increasing loop ends after committing W(n), and returns previousOne. Under the enforced bound all intermediate counts are positive and no larger than W(91), so each long addition is exact.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    private Solution() {}
    private static void validate(int n) {
        if (n < 0 || n > 91) throw new IllegalArgumentException("n must be 0..91");
    }
    public static long climbStairs(int n) {
        validate(n);
        if (n <= 1) return 1;
        long previousTwo = 1, previousOne = 1;
        for (int step = 2; step <= n; step++) {
            long next = previousTwo + previousOne;
            previousTwo = previousOne;
            previousOne = next;
        }
        return previousOne;
    }
    // Baseline: exponential recursion. Run only on small n.
    public static long baseline(int n) {
        validate(n);
        return enumerate(n);
    }
    private static long enumerate(int remaining) {
        if (remaining <= 1) return 1;
        return enumerate(remaining - 1) + enumerate(remaining - 2);
    }
}

Read the meaningful blocks

Validate before the shortcut

validate rejects negative heights and n>91 even though a naive n<=1 shortcut could accidentally accept a negative input. Both public methods apply the same validation.

Preserve both predecessors until next exists

The long temporary is necessary for the rolling update. If previousTwo were overwritten first, adding the registers would double W(s−1) instead of adding two different predecessor states.

Return the completed destination state

For n≥2 the last loop iteration calculates the requested height. Returning previousTwo would be one state behind. For n=0 or 1, the direct return is the contract result, not a loop initialization accident.

Complexity

The reference runs O(n+1) time and uses O(1) auxiliary storage with a fixed number of long registers. Output is one long. The +1 covers validation and the two base cases; the input range is finite but n remains the useful size parameter.

The baseline uses O(2^n) time and O(n+1) call-stack space. Bounds here treat long addition as constant-time because counts are explicitly limited to 64 bits. For arbitrary-precision counting, both operation cost and number of bits grow with n; an O(n) count of arithmetic operations alone is not a full bit-complexity bound.

Exact-state walkthroughs

Reveal normal and boundary traces

Five steps: preserve both predecessors

Input: 5 · Exact ordered path count: 8

Step 1 of 12: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Climbing Stairs — sum two disjoint path families

Phase: validated.

W(s) = W(s−2) + W(s−1)

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Target height: 5. W(s) counts ordered move sequences landing exactly on s. W(0)=1 includes the empty path.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`5`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 91) throw new IllegalArgumentException("n must be 0..91");
 5     }
 6     public static long climbStairs(int n) {
 7         validate(n);
 8         if (n <= 1) return 1;
 9         long previousTwo = 1, previousOne = 1;
10         for (int step = 2; step <= n; step++) {
11             long next = previousTwo + previousOne;
12             previousTwo = previousOne;
13             previousOne = next;
14         }
15         return previousOne;
16     }
17     // Baseline: exponential recursion. Run only on small n.
18     public static long baseline(int n) {
19         validate(n);
20         return enumerate(n);
21     }
22     private static long enumerate(int remaining) {
23         if (remaining <= 1) return 1;
24         return enumerate(remaining - 1) + enumerate(remaining - 2);
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
5
phase
"validated"
caseResults
[]
Seed the two counting predecessors.
The conceptual table contains W(0)=W(1)=1. Null means uncomputed, not zero or unreachable. The Java reference stores only the two-register frontier.
input
5
phase
"range-start"
caseResults
[]
table
[1,1,null,null,null,null]
previousTwo
1
previousOne
1
position
1
Add disjoint final-two and final-one move families.
Before the shift: previousTwo=W(s−2), previousOne=W(s−1). Different final moves give disjoint paths, so addition counts every path exactly once.
input
5
phase
"candidate"
caseResults
[]
table
[1,1,null,null,null,null]
previousTwo
1
previousOne
1
position
2
two
1
one
1
next
2
Commit W(s) and shift only after using both old values.
After this step the registers are W(s−1), W(s). The written table is explanatory history, not a Java allocation. Candidate values retain the old pair for comparison.
input
5
phase
"commit"
caseResults
[]
table
[1,1,2,null,null,null]
previousTwo
1
previousOne
2
position
2
two
1
one
1
next
2
Add disjoint final-two and final-one move families.
Before the shift: previousTwo=W(s−2), previousOne=W(s−1). Different final moves give disjoint paths, so addition counts every path exactly once.
input
5
phase
"candidate"
caseResults
[]
table
[1,1,2,null,null,null]
previousTwo
1
previousOne
2
position
3
two
1
one
2
next
3
Commit W(s) and shift only after using both old values.
After this step the registers are W(s−1), W(s). The written table is explanatory history, not a Java allocation. Candidate values retain the old pair for comparison.
input
5
phase
"commit"
caseResults
[]
table
[1,1,2,3,null,null]
previousTwo
2
previousOne
3
position
3
two
1
one
2
next
3
Add disjoint final-two and final-one move families.
Before the shift: previousTwo=W(s−2), previousOne=W(s−1). Different final moves give disjoint paths, so addition counts every path exactly once.
input
5
phase
"candidate"
caseResults
[]
table
[1,1,2,3,null,null]
previousTwo
2
previousOne
3
position
4
two
2
one
3
next
5
Commit W(s) and shift only after using both old values.
After this step the registers are W(s−1), W(s). The written table is explanatory history, not a Java allocation. Candidate values retain the old pair for comparison.
input
5
phase
"commit"
caseResults
[]
table
[1,1,2,3,5,null]
previousTwo
3
previousOne
5
position
4
two
2
one
3
next
5
Add disjoint final-two and final-one move families.
Before the shift: previousTwo=W(s−2), previousOne=W(s−1). Different final moves give disjoint paths, so addition counts every path exactly once.
input
5
phase
"candidate"
caseResults
[]
table
[1,1,2,3,5,null]
previousTwo
3
previousOne
5
position
5
two
3
one
5
next
8
Commit W(s) and shift only after using both old values.
After this step the registers are W(s−1), W(s). The written table is explanatory history, not a Java allocation. Candidate values retain the old pair for comparison.
input
5
phase
"commit"
caseResults
[]
table
[1,1,2,3,5,8]
previousTwo
5
previousOne
8
position
5
two
3
one
5
next
8
The final committed height is the requested count.
Every earlier destination count is exact. The finite loop leaves W(n) in previousOne; this is ordered path counting, not combination counting.
input
5
phase
"range-complete"
caseResults
[]
table
[1,1,2,3,5,8]
previousTwo
5
previousOne
8
position
5
answer
8
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
8

Empty staircase

Input: 0 · Exact ordered path count: 1

Step 1 of 3: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Climbing Stairs — sum two disjoint path families

Phase: validated.

W(s) = W(s−2) + W(s−1)

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Target height: 0. W(s) counts ordered move sequences landing exactly on s. W(0)=1 includes the empty path.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`0`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 91) throw new IllegalArgumentException("n must be 0..91");
 5     }
 6     public static long climbStairs(int n) {
 7         validate(n);
 8         if (n <= 1) return 1;
 9         long previousTwo = 1, previousOne = 1;
10         for (int step = 2; step <= n; step++) {
11             long next = previousTwo + previousOne;
12             previousTwo = previousOne;
13             previousOne = next;
14         }
15         return previousOne;
16     }
17     // Baseline: exponential recursion. Run only on small n.
18     public static long baseline(int n) {
19         validate(n);
20         return enumerate(n);
21     }
22     private static long enumerate(int remaining) {
23         if (remaining <= 1) return 1;
24         return enumerate(remaining - 1) + enumerate(remaining - 2);
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
0
phase
"validated"
caseResults
[]
The empty path and the one-step path each contribute one.
W(0)=1 is the empty-sequence identity; W(1)=1 counts [1]. No rolling loop is needed.
input
0
phase
"base"
caseResults
[]
table
[1]
answer
1
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
1

Single step

Input: 1 · Exact ordered path count: 1

Step 1 of 3: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Climbing Stairs — sum two disjoint path families

Phase: validated.

W(s) = W(s−2) + W(s−1)

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Target height: 1. W(s) counts ordered move sequences landing exactly on s. W(0)=1 includes the empty path.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`1`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 91) throw new IllegalArgumentException("n must be 0..91");
 5     }
 6     public static long climbStairs(int n) {
 7         validate(n);
 8         if (n <= 1) return 1;
 9         long previousTwo = 1, previousOne = 1;
10         for (int step = 2; step <= n; step++) {
11             long next = previousTwo + previousOne;
12             previousTwo = previousOne;
13             previousOne = next;
14         }
15         return previousOne;
16     }
17     // Baseline: exponential recursion. Run only on small n.
18     public static long baseline(int n) {
19         validate(n);
20         return enumerate(n);
21     }
22     private static long enumerate(int remaining) {
23         if (remaining <= 1) return 1;
24         return enumerate(remaining - 1) + enumerate(remaining - 2);
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
1
phase
"validated"
caseResults
[]
The empty path and the one-step path each contribute one.
W(0)=1 is the empty-sequence identity; W(1)=1 counts [1]. No rolling loop is needed.
input
1
phase
"base"
caseResults
[]
table
[1,1]
answer
1
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
1

First two-parent transition

Input: 2 · Exact ordered path count: 2

Step 1 of 6: Validate the complete input before any base-case result.

Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.

Climbing Stairs — sum two disjoint path families

Phase: validated.

W(s) = W(s−2) + W(s−1)

The complete input satisfies the documented contract. The next step establishes base states before any transition.

Target height: 2. W(s) counts ordered move sequences landing exactly on s. W(0)=1 includes the empty path.

Input entries stay unchanged. Candidate and commit steps separate reading the old frontier from updating it. Full state tables and the equivalent static walkthrough appear below.

State after this step
Variable	Value
input	`2`
phase	`"validated"`
caseResults	`[]`

See the affected Java block

 1 public final class Solution {
 2     private Solution() {}
 3     private static void validate(int n) {
 4         if (n < 0 || n > 91) throw new IllegalArgumentException("n must be 0..91");
 5     }
 6     public static long climbStairs(int n) {
 7         validate(n);
 8         if (n <= 1) return 1;
 9         long previousTwo = 1, previousOne = 1;
10         for (int step = 2; step <= n; step++) {
11             long next = previousTwo + previousOne;
12             previousTwo = previousOne;
13             previousOne = next;
14         }
15         return previousOne;
16     }
17     // Baseline: exponential recursion. Run only on small n.
18     public static long baseline(int n) {
19         validate(n);
20         return enumerate(n);
21     }
22     private static long enumerate(int remaining) {
23         if (remaining <= 1) return 1;
24         return enumerate(remaining - 1) + enumerate(remaining - 2);
25     }
26 }
27

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the complete input before any base-case result.
Bounds, null, and value rules belong to the API. These displayed fixtures satisfy the contract; no caller input is changed.
input
2
phase
"validated"
caseResults
[]
Seed the two counting predecessors.
The conceptual table contains W(0)=W(1)=1. Null means uncomputed, not zero or unreachable. The Java reference stores only the two-register frontier.
input
2
phase
"range-start"
caseResults
[]
table
[1,1,null]
previousTwo
1
previousOne
1
position
1
Add disjoint final-two and final-one move families.
Before the shift: previousTwo=W(s−2), previousOne=W(s−1). Different final moves give disjoint paths, so addition counts every path exactly once.
input
2
phase
"candidate"
caseResults
[]
table
[1,1,null]
previousTwo
1
previousOne
1
position
2
two
1
one
1
next
2
Commit W(s) and shift only after using both old values.
After this step the registers are W(s−1), W(s). The written table is explanatory history, not a Java allocation. Candidate values retain the old pair for comparison.
input
2
phase
"commit"
caseResults
[]
table
[1,1,2]
previousTwo
1
previousOne
2
position
2
two
1
one
1
next
2
The final committed height is the requested count.
Every earlier destination count is exact. The finite loop leaves W(n) in previousOne; this is ordered path counting, not combination counting.
input
2
phase
"range-complete"
caseResults
[]
table
[1,1,2]
previousTwo
1
previousOne
2
position
2
answer
2
Return the exact value required by the contract.
Teaching tables and saved candidate values explain the dependency frontier; they are excluded from the Java reference’s constant auxiliary storage.
result
2

Test the contract

Input: n=1
Output: 1
Only [1].
Input: n=2
Output: 2
[1,1] and [2].
Input: n=10
Output: 89
Checks multiple rolling transitions.
Input: n=46
Output: 2971215073
Detects int overflow.
Input: n=-1
Output: IllegalArgumentException
Validation precedes the small-height shortcut.
Input: n=92
Output: IllegalArgumentException
Exact long contract boundary.

Common mistakes and counterexamples

Set W(0)=0

Counterexample: For n=2 the path [2] extends the zero-height prefix; deleting that prefix undercounts.

Use one empty sequence as the additive construction identity.

Count combinations instead of ordered paths

Counterexample: For n=3, [1,2] and [2,1] are distinct; a coin-type outer loop can count them as one.

Partition by the final move of ordered sequences, rather than by denomination quantities.

Shift registers before computing next

Counterexample: At step 3, replacing previousTwo by 2 before adding can produce 4 instead of 3.

Calculate next using the old pair, then shift in the documented order.

Use int or allow n=92 with long

Counterexample: W(46)=2971215073 exceeds int; W(92)=12200160415121876738 exceeds long.

Keep an exact long result and enforce 0..91, or explicitly redesign for BigInteger.

Follow-ups

Allow a configurable set of positive step sizes.

Define W(0)=1 and W(s)=sum W(s−d) over legal positive d≤s. Deduplicate equal step sizes if equal distances are not distinct move types. A table costs O(nm) operations for m sizes; a rolling buffer needs enough history for the largest step. State a numeric bound or use modular/BigInteger arithmetic.

Some steps are forbidden landing points.

Set W(s)=0 for a forbidden destination and otherwise apply the same predecessor sum. Decide whether ground or top may be forbidden and check those bases explicitly. The recurrence still counts paths, but the unmodified Fibonacci closed form no longer applies.

Answer enormous n or many queries.

For many bounded queries, precompute once and answer in O(1). For enormous n, use Fibonacci fast doubling or matrix exponentiation with BigInteger or a specified modulus. Logarithmically many arithmetic steps does not make multiplication on large exact integers constant-time.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.