509. Fibonacci Number

LeetCode 509: Fibonacci Number Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses an iterative bottom-up approach (Dynamic Programming) to calculate the $n$-th value by summing the two previous values, reducing the time complexity to linear and space to constant.

The Fibonacci Number problem asks us to compute the $n$-th term in the Fibonacci sequence. The sequence is defined recursively where each number is the sum of the two preceding ones. Specifically, $F(0) = 0$, $F(1) = 1$, and for any $n > 1$, $F(n) = F(n-1) + F(n-2)$. While the mathematical definition is recursive, LeetCode 509 serves as a fundamental introduction to optimizing recursive problems using Dynamic Programming.

Brute Force Approach for Fibonacci Number

The most intuitive way to solve the Fibonacci Number problem is to directly translate the mathematical recurrence relation into code using recursion.

The algorithm functions as follows:

1. Check if $n$ is 0 or 1. If so, return $n$.
2. Otherwise, recursively call the function for $n-1$ and $n-2$ and return their sum.

1# Pseudo-code for Brute Force
2function fib(n):
3    if n <= 1:
4        return n
5    return fib(n - 1) + fib(n - 2)

Why this approach fails: The time complexity of this recursive solution is $O(2^n)$. This exponential growth occurs because the algorithm re-calculates the same subproblems multiple times. For example, to calculate $F(5)$, it calculates $F(4)$ and $F(3)$. However, the calculation of $F(4)$ also calculates $F(3)$. As $n$ increases, the number of redundant operations explodes, leading to a Time Limit Exceeded (TLE) on larger constraints or significant inefficiency on moderate ones.

Algorithm Strategy: Dynamic Programming (DP) Patterns

The strategy utilizes the DP - 1D Array subpattern with a space optimization.

1. State Definition: Let dp[i] represent the $i$-th Fibonacci number.
2. Recurrence Relation: dp[i] = dp[i-1] + dp[i-2].
3. Base Cases: dp[0] = 0, dp[1] = 1.
4. Space Optimization: Notice that to calculate dp[i], we only need dp[i-1] and dp[i-2]. We do not need to access dp[i-3] or any earlier values. Therefore, we do not need to maintain the entire array in memory. We can maintain just two variables, prev2 (representing $F(i-2)$) and prev1 (representing $F(i-1)$), and update them iteratively.

This transforms the space complexity from $O(n)$ (using an array) to $O(1)$ (using variables), which is the optimal solution for interviews.

Execution Flow

1. Handle Base Cases: If $n = 0$, return 0. If $n = 1$, return 1.
2. Initialize State:
   • Set prev2 = 0 (corresponds to $F(0)$).
   • Set prev1 = 1 (corresponds to $F(1)$).
3. Iterate: Loop from $i = 2$ up to $n$.
   • Calculate current = prev1 + prev2.
   • Update pointers for the next iteration:
     • prev2 becomes the old prev1.
     • prev1 becomes the calculated current.
4. Return Result: After the loop finishes, prev1 holds the value of $F(n)$.

Proof of Correctness

The correctness is proven via mathematical induction.

• Base Case: The algorithm explicitly handles or initializes correctly for $n=0$ and $n=1$.
• Inductive Step: Assume that at iteration $i$, prev1 correctly holds $F(i-1)$ and prev2 correctly holds $F(i-2)$. The algorithm computes current = prev1 + prev2, which is $F(i-1) + F(i-2)$. By the definition of the Fibonacci sequence, this sum is exactly $F(i)$.
• Termination: The loop terminates at $n$, ensuring the final value stored in prev1 is $F(n)$.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern is foundational. The logic of depending on the previous one or two states applies directly to:

• LeetCode 70: Climbing Stairs (Identical recurrence: $ways(i) = ways(i-1) + ways(i-2)$)
• LeetCode 91: Decode Ways (Conditional recurrence based on previous 1 or 2 digits)
• LeetCode 198: House Robber (Choice between robbing current house + $dp[i-2]$ vs skipping current house + $dp[i-1]$)
• LeetCode 213: House Robber II (Same logic as House Robber, with circular array handling)

Reference Implementation

C++ Solution for LeetCode 509

1class Solution {
2public:
3    int fib(int n) {
4        // Base cases
5        if (n == 0) return 0;
6        if (n == 1) return 1;
7
8        // DP state variables
9        int prev2 = 0; // F(0)
10        int prev1 = 1; // F(1)
11        
12        // Iterative Bottom-Up Calculation
13        for (int i = 2; i <= n; ++i) {
14            int current = prev1 + prev2;
15            prev2 = prev1;
16            prev1 = current;
17        }
18        
19        return prev1;
20    }
21};

Java Solution for LeetCode 509

1class Solution {
2    public int fib(int n) {
3        // Base cases
4        if (n == 0) return 0;
5        if (n == 1) return 1;
6
7        // DP state variables
8        int prev2 = 0; // F(0)
9        int prev1 = 1; // F(1)
10
11        // Iterative Bottom-Up Calculation
12        for (int i = 2; i <= n; i++) {
13            int current = prev1 + prev2;
14            prev2 = prev1;
15            prev1 = current;
16        }
17
18        return prev1;
19    }
20}

Python Solution for LeetCode 509

1class Solution:
2    def fib(self, n: int) -> int:
3        # Base cases
4        if n == 0:
5            return 0
6        if n == 1:
7            return 1
8        
9        # DP state variables
10        prev2, prev1 = 0, 1
11        
12        # Iterative Bottom-Up Calculation
13        for _ in range(2, n + 1):
14            current = prev1 + prev2
15            prev2 = prev1
16            prev1 = current
17            
18        return prev1