How to Solve: Fibonacci Number (Top-Down, Bottom-Up, Space Optimization) – Complete Guide

How to Solve: Fibonacci Number (Top-Down, Bottom-Up, Space Optimization) – Complete Guide

? Introduction

"This single problem tests recursion, memoization, dynamic programming, and space optimization—master it, and you’ll crush 1 out of every 3 FAANG onsite interviews where DP comes up."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Recursion – Base cases, recursive calls, call stack. 2. Memoization (Caching) – Storing computed results to avoid redundant work. 3. Dynamic Programming (DP) – Breaking problems into overlapping subproblems.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental checklist for every Fibonacci problem:

1. Clarify the problem:
2. Is fib(0) = 0 or 1? (Standard: fib(0) = 0, fib(1) = 1.)

3. What’s the input range? (If n ≤ 30, recursion is fine. If n ≥ 1000, use DP.)

4. Write the recursive formula:

5. fib(n) = fib(n-1) + fib(n-2)

6. Base cases: fib(0) = 0, fib(1) = 1

7. Check for overlapping subproblems:

8. If fib(n) is computed multiple times, memoization is needed.

9. Choose the right approach:

10. Small n (≤30): Recursion (naive).
11. Medium n (≤1000): Top-down (memoization) or bottom-up (tabulation).

12. Large n (10⁶+): Space-optimized DP or matrix exponentiation.

13. Implement & test edge cases:

14. n = 0, n = 1, n = 2, n = 5, n = 10.

15. Check for integer overflow (use long if needed).

16. Optimize space (if required):

17. If space is O(n), can it be reduced to O(1)?

? WORKED EXAMPLES

Example 1 – Basic: Recursive (Naive)

Problem: Compute the nth Fibonacci number (naive recursion).

Thought Process: - Directly implement the recursive formula. - Time: O(2ⁿ) (exponential, inefficient). - Space: O(n) (call stack depth).

Code (Python):

def fib(n: int) -> int:

    if n == 0:

        return 0

    if n == 1:

        return 1

    return fib(n - 1) + fib(n - 2)

Why this works: - Follows the mathematical definition directly. - But: Fails for n > 30 due to exponential time.

Example 2 – Medium: Top-Down (Memoization)

Problem: Optimize the recursive solution using memoization.

Thought Process: - Store computed fib(n) in a hash map to avoid recomputation. - Time: O(n) (each fib(i) computed once). - Space: O(n) (memoization table + call stack).

Code (Python):

def fib(n: int, memo={}) -> int:

    if n in memo:

        return memo[n]

    if n == 0:

        return 0

    if n == 1:

        return 1

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)

    return memo[n]

Why this works: - Eliminates redundant recursive calls by caching results. - Tradeoff: Still uses O(n) space due to recursion stack.

Example 3 – Hard: Bottom-Up (Tabulation) + Space Optimization

Problem: Compute fib(n) in O(n) time and O(1) space.

Thought Process: 1. Bottom-Up (Tabulation):
- Iteratively compute fib(0) to fib(n) in an array.
- Time: O(n), Space: O(n). 2. Space Optimization:
- Only track the last two values (prev1, prev2).
- Time: O(n), Space: O(1).

Code (Python):

# Bottom-Up (Tabulation)
def fib(n: int) -> int:

    if n == 0:

        return 0

    dp = [0]  (n + 1)

    dp[1] = 1

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

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

    return dp[n]

# Space-Optimized
def fib(n: int) -> int:

    if n == 0:

        return 0

    prev2, prev1 = 0, 1

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

        curr = prev1 + prev2

        prev2, prev1 = prev1, curr

    return prev1

Why this works: - Tabulation: Builds the solution iteratively, avoiding recursion stack issues. - Space Optimization: Only stores the last two values, reducing space to O(1).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. The Fibonacci problem is your gateway to dynamic programming. Here’s the playbook:

1. Start with recursion—it’s the easiest to write but only works for small n.
2. Optimize with memoization—cache results to avoid recomputation.
3. Switch to bottom-up DP—iterative, no recursion stack issues.
4. Squeeze space to O(1)—track only the last two values.
5. Test edge cases—n=0, n=1, and large n.

If the interviewer asks for space optimization, you now know how to drop from O(n) to O(1). If they ask for time complexity, you can confidently say O(n) for DP and O(2ⁿ) for naive recursion. Walk in, write the code, and own the problem. You’ve got this!

? Final Notes

• Practice: Implement all 3 approaches (recursive, memoization, space-optimized) in under 10 minutes.
• Follow-ups: Be ready for "What if n is very large?" (matrix exponentiation) or "Can you do it in O(log n) time?" (advanced).
• Whiteboard: Draw the recursion tree for fib(5) to visualize overlapping subproblems.

Now go crush that interview! ?