Cracking The Coding Interview Together – Problem 8.1: Triple Step

At first glance, stair-climbing problems feel like simple toy puzzles. A child is hopping up a staircase, choosing between one, two, or three steps per leap, and we need to count the total distinct sequences that reach the top. However, underestimating this problem in an interview is a classic trap.

What begins as a seemingly harmless recursive problem quickly cascades into an exponential time complexity nightmare ($O(3^n)$) that crashes your runtime for values as low as $n = 35$. The core conflict here is managing overlapping subproblems without blowing up memory or overflowing standard primitive types. In this guide, our goal is to build an intuitive mental model for Dynamic Programming (DP), transitioning systematically from naive recursion to memoization, bottom-up tabulation, and finally, an optimal $O(1)$ space solution.

Problem Statement

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

Operational Goals:

• Input: A single integer n representing the total number of steps.
• Output: An integer (or appropriate numeric type) representing the total number of valid permutations of step sequences to reach step n.
• Handle non-positive inputs gracefully and consider integer overflow for large values of n.

Analyze the Problem Together

Let's dissect how the child can land on the final $n$-th step. Think about the very last leap made before reaching step $n$:

• They could have jumped 1 step from step $(n - 1)$.
• They could have jumped 2 steps from step $(n - 2)$.
• They could have jumped 3 steps from step $(n - 3)$.

Because these three scenarios are mutually exclusive and cover every possible final move, the total ways to reach step $n$, denoted as $ways(n)$, is simply the sum of the ways to reach each of those preceding landing pads:

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

This is a direct generalization of the Fibonacci sequence—often referred to as a Tribonacci series.

Let's compare the architectural approaches to solving this recurrence:

Questions for the Interviewer

Before jumping straight into coding, demonstrating seniority means clarifying edge constraints upfront:

1. How should we handle $n = 0$ or negative values? Is reaching a 0-step staircase considered 1 way (standing still) or 0 ways? (Conventionally, $ways(0) = 1$ in combinatorial terms, but programmatic inputs often treat $n \le 0$ as 0 valid steps).
2. What are the expected bounds for $n$? Since the Tribonacci sequence grows exponentially, standard 32-bit signed integers (int) overflow around $n = 37$. Do we need to return a long, a BigInteger, or return the result modulo $10^9 + 7$?
3. Can the step sizes change dynamically? Would the algorithm need to support a variable list of allowed step sizes (e.g., $k \in \{1, 2, 5\}$), or is the set strictly fixed to $\{1, 2, 3\}$?

Think About the Solution

Let's map out the state transitions. To compute $ways(n)$, we only ever need the values of the last three states:

• Base case 1: $n = 0 \rightarrow 1$ (1 way to stay at the start ground level).
• Base case 2: $n = 1 \rightarrow 1$ (only sequence: [1]).
• Base case 3: $n = 2 \rightarrow 2$ (sequences: [1, 1], [2]).

For $n = 3$, $ways(3) = ways(2) + ways(1) + ways(0) = 2 + 1 + 1 = 4$ (sequences: [1, 1, 1], [1, 2], [2, 1], [3]).

Instead of maintaining an entire array of size $n+1$, we maintain three variables: a ($ways(i-3)$), b ($ways(i-2)$), and c ($ways(i-1)$). In each iteration from $3$ up to $n$, we compute current = a + b + c, slide our window forward, and achieve $O(1)$ auxiliary space complexity.

Write Code and Explain

Here is the production-ready Java implementation containing both the top-down memoized variation for conceptual clarity and the optimal $O(1)$ space iterative solution, including integer overflow handling using long.

public class TripleStep {

    /**
     * Optimal Space-Efficient Approach (Bottom-Up Tabulation with Rolling Variables)
     * Time Complexity: O(n)
     * Auxiliary Space Complexity: O(1)
     */
    public static long countWaysOptimal(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        // Base states: ways(0) = 1, ways(1) = 1, ways(2) = 2
        long step0 = 1; 
        long step1 = 1; 
        long step2 = 2; 
        long current = 0;

        for (int i = 3; i <= n; i++) {
            current = step0 + step1 + step2;
            // Slide window forward
            step0 = step1;
            step1 = step2;
            step2 = current;
        }

        return current;
    }

    /**
     * Top-Down Approach with Memoization (Helpful for variable step sizes)
     * Time Complexity: O(n)
     * Auxiliary Space Complexity: O(n)
     */
    public static long countWaysMemoized(int n) {
        if (n < 0) {
            return 0;
        }
        long[] memo = new long[n + 1];
        java.util.Arrays.fill(memo, -1);
        return countWaysMemoHelper(n, memo);
    }

    private static long countWaysMemoHelper(int n, long[] memo) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        if (memo[n] > -1) {
            return memo[n];
        }

        memo[n] = countWaysMemoHelper(n - 1, memo) 
                + countWaysMemoHelper(n - 2, memo) 
                + countWaysMemoHelper(n - 3, memo);

        return memo[n];
    }
}

Step-by-Step Walkthrough:

1. Guards and Base Cases: We first guard against negative inputs, which immediately return 0. The base cases for n = 0, 1, 2 are resolved immediately without loop execution.
2. Rolling Window: In countWaysOptimal, variables step0, step1, and step2 hold the answers for the previous 3 steps.
3. State Progression: Inside our single loop running from $3$ to $n$, we sum the variables into current, shift step0 ← step1, step1 ← step2, and step2 ← current.
4. Return: After completing the loop, current holds the exact count of combinations for step $n$.

Time & Space Complexity

Time Complexity: $O(n)$
We execute a single loop from 3 up to $n$. Each iteration performs simple constant-time addition and assignment operations ($O(1)$). Thus, the runtime scales strictly linearly with $n$.

Auxiliary Space Complexity: $O(1)$
Unlike recursive implementations that incur an $O(n)$ call stack, or array-based tabulation requiring $O(n)$ heap allocation, the rolling variable method only instantiates four primitive long variables, using strictly constant space.

Why This Problem Matters (The Senior Perspective)

The Triple Step problem is the quintessential introduction to Dynamic Programming, but in production systems, the exact same recurrence logic underpins critical real-world architectures:

• Rate Limiter Token Buckets & Leaky Buckets: Sliding window calculations over discrete event slots rely on maintaining fixed history buffers rather than re-computing aggregated states from scratch.
• Finite State Machine (FSM) Transitions: When tracking transitions across sequential state dependencies (like multi-step checkout funnels or workflow state validation), rolling state updates prevent memory bloat.
• Numerical Stability & Overflows: In high-throughput distributed systems, unchecked integer accumulations lead to silent wrapping bugs (e.g., positive counts turning negative). Recognizing when values scale exponentially allows us to plan for 64-bit integers, modulo arithmetic, or arbitrary-precision libraries like BigInteger early.

Final Thoughts

Whenever you face a combinatorial counting problem, resist the urge to remain at the level of brute-force recursion. Break down the dependencies, draw the recursion tree, identify repeated work, and compress your memory profile to only what is strictly necessary to compute the next state.

As an exercise to test your understanding: How would you modify this solution if the allowed step sizes were given dynamically as an arbitrary array steps = [1, 3, 5]? Give that a try, and happy coding!