Climbing Stairs LeetCode Solution in JavaScript and TypeScript

The Climbing Stairs problem is a fundamental algorithmic challenge that introduces developers to dynamic programming concepts. This comprehensive guide will walk you through various approaches to solve this popular LeetCode problem (#70) using TypeScript, while explaining the underlying concepts and optimization techniques.

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

1Input: n = 2
2Output: 2
3Explanation: There are two ways to climb to the top:
41. 1 step + 1 step
52. 2 steps

Example 2:

1Input: n = 3
2Output: 3
3Explanation: There are three ways to climb to the top:
41. 1 step + 1 step + 1 step
52. 1 step + 2 steps
63. 2 steps + 1 step

Understanding the Problem

The Climbing Stairs problem is essentially a variation of the Fibonacci sequence. The key insight is that to reach any step n, you can only come from either step (n-1) or step (n-2). Therefore, the total number of ways to reach step n is the sum of ways to reach step (n-1) and step (n-2).

There are several approaches to solve this problem:

1. Recursive Solution (Time: O(2ⁿ), Space: O(n))
2. Dynamic Programming (Time: O(n), Space: O(n))
3. Optimized Dynamic Programming (Time: O(n), Space: O(1))
4. Mathematical Solution using Fibonacci (Time: O(n), Space: O(1))

Let's implement each approach and discuss their trade-offs.

TypeScript Implementation

1. Recursive Solution (Not Recommended for Large Inputs)

1function climbStairs(n: number): number {
2    // Base cases
3    if (n <= 2) return n;
4    
5    // Recursive case
6    return climbStairs(n - 1) + climbStairs(n - 2);
7}

While this solution is intuitive, it has exponential time complexity and will timeout for larger inputs due to redundant calculations.

2. Dynamic Programming Solution

1function climbStairs(n: number): number {
2    // Handle base cases
3    if (n <= 2) return n;
4    
5    // Create DP array to store intermediate results
6    const dp: number[] = new Array(n + 1);
7    
8    // Initialize base cases
9    dp[1] = 1;
10    dp[2] = 2;
11    
12    // Fill the DP array
13    for (let i = 3; i <= n; i++) {
14        dp[i] = dp[i - 1] + dp[i - 2];
15    }
16    
17    return dp[n];
18}

3. Space-Optimized Solution (Recommended)

1function climbStairs(n: number): number {
2    // Handle base cases
3    if (n <= 2) return n;
4    
5    // Initialize variables for previous two steps
6    let oneStepBefore: number = 2;
7    let twoStepsBefore: number = 1;
8    let allWays: number = 0;
9    
10    // Calculate ways for remaining steps
11    for (let i = 3; i <= n; i++) {
12        allWays = oneStepBefore + twoStepsBefore;
13        twoStepsBefore = oneStepBefore;
14        oneStepBefore = allWays;
15    }
16    
17    return allWays;
18}
19
20// Example usage
21console.log(climbStairs(2));  // Output: 2
22console.log(climbStairs(3));  // Output: 3
23console.log(climbStairs(4));  // Output: 5

Code Analysis and Complexity

Let's analyze our optimized solution:

Time Complexity

• O(n) - We iterate through the steps once
• No recursive calls or redundant calculations

Space Complexity

• O(1) - We only use three variables regardless of input size
• No additional data structures needed

Understanding the Mathematics

The solution follows the Fibonacci sequence pattern:

• F(n) = F(n-1) + F(n-2)
• For n steps: ways(n) = ways(n-1) + ways(n-2)

Sequence for first few steps:

• n = 1: 1 way
• n = 2: 2 ways
• n = 3: 3 ways
• n = 4: 5 ways
• n = 5: 8 ways

Performance Optimization Tips

1. Memoization

   • Use memoization for recursive solutions
   • Cache previously calculated results

2. Variable Optimization

   • Use number type instead of bigint unless necessary
   • Avoid array allocation for simple cases

3. Early Returns

   • Handle base cases immediately
   • Validate input constraints

Common Edge Cases and Input Validation

1function climbStairs(n: number): number {
2    // Input validation
3    if (!Number.isInteger(n) || n < 0) {
4        throw new Error('Input must be a non-negative integer');
5    }
6    
7    // Handle base cases
8    if (n <= 2) return n;
9    
10    let [a, b] = [1, 2];
11    for (let i = 3; i <= n; i++) {
12        [a, b] = [b, a + b];
13    }
14    
15    return b;
16}

Related Problems

• House Robber (LeetCode #198)
• Fibonacci Number (LeetCode #509)
• Min Cost Climbing Stairs (LeetCode #746)

External Resources

• Original LeetCode Problem
• Dynamic Programming on Wikipedia
• Fibonacci Sequence
• Time Complexity Analysis

Interview Tips

When solving this problem in an interview:

1. Start with the brute force approach to show problem-solving process
2. Explain the optimization steps clearly
3. Discuss space-time complexity trade-offs
4. Consider edge cases and input validation
5. Mention real-world applications of similar patterns

Related Concepts

• Dynamic Programming
• Fibonacci Sequence
• Memoization
• Space-Time Complexity Trade-offs
• Recursive vs Iterative Solutions

Conclusion

The Climbing Stairs problem is an excellent introduction to dynamic programming and optimization techniques. While the problem may seem simple at first, it teaches important concepts about algorithm optimization and the relationship between recursive and iterative solutions.

Understanding this problem helps build a strong foundation for more complex dynamic programming challenges and demonstrates the importance of recognizing patterns in algorithmic problem-solving.

Remember to practice with different input sizes and edge cases to fully grasp the implementation details and optimization opportunities. This problem frequently appears in technical interviews at top tech companies, making it essential for interview preparation.