Skip to main content

509 - Fibonacci Number

Difficulty: Easy | Pattern: Recursion / DP / Math | Company tags: Amazon, Apple

Problem Statement​

The Fibonacci numbers, commonly denoted F(n), form a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1:

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

Given n, calculate F(n).

Example 1: F(2) = 1 (0, 1, 1) Example 2: F(3) = 2 (0, 1, 1, 2) Example 3: F(4) = 3 (0, 1, 1, 2, 3)

Constraints: 0 <= n <= 30

Four Approaches (from Slow to Fast)​

Approach 1: Naive Recursion — O(2^n) time (exponential, DO NOT USE)​

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Problem: Exponential time — recomputes the same subproblems. fib(40) makes ~2 billion calls.

Approach 2: Memoization (Top-Down DP) — O(n) time, O(n) space​

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Or manually:

def fib(n: int) -> int:
    memo = {}
    def helper(k):
        if k <= 1:
            return k
        if k not in memo:
            memo[k] = helper(k-1) + helper(k-2)
        return memo[k]
    return helper(n)

Approach 3: Bottom-Up DP — O(n) time, O(n) space​

def fib(n: int) -> int:
    if n <= 1:
        return n
    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]

Approach 4: Space-Optimized DP — O(n) time, O(1) space​

def fib(n: int) -> int:
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

This is the best solution — O(n) time, O(1) space.

Algorithm Flow​

Complexity Comparison​

ApproachTimeSpace
Naive recursionO(2^n)O(n) call stack
MemoizationO(n)O(n)
Bottom-up DPO(n)O(n)
Space-optimizedO(n)O(1)

Teaching Value​

This problem introduces three fundamental DP concepts:

  1. Overlapping subproblems: The same sub-problem is computed multiple times in naive recursion
  2. Memoization: Cache results to avoid recomputation (top-down)
  3. Tabulation: Build up from base cases (bottom-up) — often simpler to reason about

Key Terms​

TermDefinition
Overlapping subproblemsThe same smaller input recurs many times during recursion, making naive recomputation wasteful.
MemoizationTop-down caching of subproblem results (e.g. via lru_cache or a dict) so each value is computed once.
TabulationBottom-up DP that fills an array from base cases upward, avoiding recursion overhead entirely.
Space optimizationReducing an O(n) DP array to O(1) by keeping only the last two states needed for the next computation.

FAQ​

  1. Can this be solved without extra space? Yes — the space-optimized iterative version keeps only prev and curr, achieving O(1) space and O(n) time.
  2. What if n is 0? F(0) = 0 by definition; the base-case check if n <= 1: return n handles it directly.
  3. How would this change if n could be very large (e.g. n = 10^9)? Iterative O(n) would be too slow; you'd use matrix exponentiation on [[1,1],[1,0]] or Binet's formula for O(log n) time.
  4. Why avoid naive recursion in an interview even though it's "correct"? It's exponential — O(2^n) — because it recomputes the same subproblems repeatedly, which is precisely the motivation for introducing memoization.
  5. Is memoization or tabulation preferred here? For this problem, space-optimized iteration is best overall; between the two DP styles, tabulation avoids recursion/call-stack overhead, while memoization is more natural when the recursion tree is irregular.

Quick Revision​

  • Problem: compute the nth Fibonacci number, F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1.
  • Naive recursion is O(2^n) — recomputes overlapping subproblems, avoid in interviews.
  • Memoization (top-down): cache each fib(k) the first time it's computed — O(n) time, O(n) space.
  • Tabulation (bottom-up): fill a dp array from base cases upward — O(n) time, O(n) space.
  • Space-optimized: track only prev and curr, update in a loop — O(n) time, O(1) space (best answer).
  • This problem is the canonical teaching example for overlapping subproblems and DP.
  • For very large n, matrix exponentiation gives O(log n) time.
  • Always state the space-optimized version as your final answer unless asked for alternatives.