Fibonacci Sequence

LeetCode #509 [Easy]

Problem Statement

Return the nth Fibonacci number, where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).

Example: Input: n = 6 ā†’ Output: 8

Approach 1: Simple Recursion

Explanation: Directly apply the Fibonacci formula recursively.

Time Complexity: O(2āæ)

Space Complexity: O(n) (stack)

function fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

šŸ’” Think: Apply the definition F(n)=F(nāˆ’1)+F(nāˆ’2) recursively until base cases.

Approach 2: Memoization (Top-Down DP)

Explanation: Store computed Fibonacci numbers to avoid recomputation.

Time Complexity: O(n)

Space Complexity: O(n) (stack + memo)

memo = {}
function fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

šŸ’” Think: Store computed Fibonacci values in a dictionary to prevent redundant calls.

Approach 3: Iterative / Bottom-Up

Explanation: Use a loop to calculate Fibonacci numbers sequentially.

Time Complexity: O(n)

Space Complexity: O(1)

a = 0, b = 1
for i from 2 to n:
    c = a + b
    a = b
    b = c
return b if n>0 else 0

šŸ’” Think: Build the sequence iteratively using two variables for constant space.

Solve on LeetCode