How to Solve: Climbing Stairs – Complete Guide for FAANG Interviews

How to Solve: Climbing Stairs – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll instantly demonstrate dynamic programming maturity while solving a classic that stumps 60% of candidates."

? WHAT YOU NEED TO KNOW FIRST

Before tackling "Climbing Stairs," ensure you understand: 1. Recursion – Base cases, recursive calls, and call stack. 2. Memoization (Top-Down DP) – Caching repeated subproblems to avoid exponential time. 3. Dynamic Programming (Bottom-Up DP) – Iterative approach to build solutions from smaller subproblems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental checklist for every "Climbing Stairs" problem:

1. Understand the Problem

2. Read the problem carefully. Confirm:

   • Can you take 1 or 2 steps at a time? (Default)
   • Are there constraints (e.g., no two consecutive same steps)?
   • What is the input range (e.g., 1 <= n <= 45)?

3. Identify the Pattern

4. Write out small cases (n=1,2,3,4) to see if it matches Fibonacci.

5. If n=1 → 1, n=2 → 2, n=3 → 3, n=4 → 5, then it’s Fibonacci(n+1).

6. Choose the Right Approach

7. Brute Force (Recursion) → Only for small n (e.g., n ≤ 20).
8. Memoization (Top-Down DP) → Good for medium n (e.g., n ≤ 45).
9. Bottom-Up DP → Best for large n (e.g., n ≤ 10⁵).

10. Space Optimization → If asked to optimize space (O(1)).

11. Implement the Solution

12. For recursion, define base cases (n=1 and n=2).
13. For memoization, use a dictionary or array to cache results.
14. For bottom-up DP, initialize dp[1] and dp[2], then iterate from 3 to n.

15. For space optimization, replace dp[] with two variables.

16. Test Edge Cases

17. n=1 → 1
18. n=2 → 2
19. n=3 → 3

20. n=45 → 1836311903 (max constraint in LeetCode)

21. Optimize Further (If Needed)

22. If asked for O(1) space, replace dp[] with variables.

23. If asked for k steps, generalize the recurrence.

24. Explain Time & Space Complexity

25. Brute Force: O(2ⁿ) time, O(n) space (call stack).
26. Memoization: O(n) time, O(n) space.
27. Bottom-Up DP: O(n) time, O(n) space.
28. Space-Optimized DP: O(n) time, O(1) space.

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 70: Climbing Stairs)

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

Solution (Bottom-Up DP):

def climbStairs(n: int) -> int:

    if n == 1:

        return 1

    dp = [0]  (n + 1)

    dp[1] = 1

    dp[2] = 2

    for i in range(3, n + 1):

        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Time Complexity: O(n) Space Complexity: O(n)

Why This Works: - The problem follows the Fibonacci sequence (dp[n] = dp[n-1] + dp[n-2]). - We build the solution iteratively to avoid recursion stack overhead.

Example 2 – Medium (Space Optimization)

Problem: Same as above, but optimize space to O(1).

Solution:

def climbStairs(n: int) -> int:

    if n == 1:

        return 1

    prev1, prev2 = 1, 2

    for _ in range(3, n + 1):

        curr = prev1 + prev2

        prev1, prev2 = prev2, curr

    return prev2

Time Complexity: O(n) Space Complexity: O(1)

Why This Works: - Instead of storing the entire dp[] array, we only keep track of the last two values (prev1 and prev2). - This reduces space from O(n) → O(1).

Example 3 – Hard/Follow-Up (Generalized k Steps)

Problem: You can climb 1, 2, or 3 steps at a time. How many distinct ways can you reach the top?

Solution (Bottom-Up DP):

def climbStairs(n: int) -> int:

    if n == 1:

        return 1

    if n == 2:

        return 2

    if n == 3:

        return 4

    dp = [0]  (n + 1)

    dp[1], dp[2], dp[3] = 1, 2, 4

    for i in range(4, n + 1):

        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    return dp[n]

Time Complexity: O(n) Space Complexity: O(n)

Why This Works: - The recurrence generalizes to dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. - We initialize the first three values (1, 2, 4) and build up.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. The ‘Climbing Stairs’ problem is Fibonacci in disguise. Here’s your 30-second cheat sheet:

1. Recognize the pattern – Small cases (n=1,2,3,4) reveal the Fibonacci sequence.
2. Choose your weapon –
3. Brute force? Only for tiny n.
4. Memoization? Good for medium n.
5. Bottom-up DP? Best for large n.
6. O(1) space? Replace dp[] with two variables.
7. Generalize if needed – If steps change (e.g., 1, 2, or 3), update the recurrence.
8. Test edge cases – Always check n=1 and n=2.
9. Explain complexity – O(n) time, O(1) space if optimized.

Now go crush that interview. You’ve got this!

? Final Notes

• Practice Variations:
• LeetCode 70 (Climbing Stairs)
• LeetCode 746 (Min Cost Climbing Stairs)
• LeetCode 91 (Decode Ways) (Similar DP pattern)
• Key Takeaway: "Climbing Stairs is a gateway to dynamic programming. Master it, and you’ll recognize DP patterns in 90% of follow-ups."