Fibonacci Number - Solution & Explanation
Problem Statement
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Example 1:
Input: n = 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: n = 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: n = 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Constraints:
0 <= n <= 30
Approach Overview
Problem Overview: The task is to compute the nth Fibonacci number. The sequence starts with F(0) = 0 and F(1) = 1. Every next value is the sum of the previous two: F(n) = F(n-1) + F(n-2). Given an integer n, return the value at that position in the sequence.
Approach 1: Recursive Approach (Time: O(2^n), Space: O(n))
The most direct implementation follows the mathematical definition. Call the function recursively for n-1 and n-2, then add their results. Base cases return 0 for n = 0 and 1 for n = 1. While this version is simple, it recomputes the same subproblems repeatedly. For example, calculating F(5) recomputes F(3) and F(2) multiple times. The recursion tree grows exponentially, which leads to O(2^n) time complexity and O(n) call stack space. This approach mainly demonstrates the structure of the recurrence and basic recursion.
Approach 2: Dynamic Programming (Time: O(n), Space: O(n))
The inefficiency in the recursive solution comes from repeated subproblems. Dynamic programming fixes this by storing previously computed Fibonacci values. Build an array where dp[i] stores F(i). Initialize dp[0] = 0 and dp[1] = 1, then iterate from 2 to n and compute dp[i] = dp[i-1] + dp[i-2]. Each Fibonacci number is calculated once, giving linear time complexity O(n). The array requires O(n) additional space. This method removes redundant computation and is the standard bottom‑up DP solution.
An alternative DP variant uses memoization. Instead of building the table iteratively, recursion stores computed results in a cache. Future recursive calls reuse those values instead of recalculating them. Time complexity becomes O(n), matching the iterative DP approach.
Recommended for interviews: Start by explaining the recursive recurrence to show understanding of the sequence definition. Then move to the dynamic programming solution. Interviewers typically expect the O(n) DP approach because it removes exponential recomputation while keeping the implementation straightforward.
Approach 1: Recursive Approach
The recursive approach involves directly applying the Fibonacci formula: F(n) = F(n-1) + F(n-2). This approach naturally follows the definition of the Fibonacci sequence, solving subproblems by calling itself. However, this naive implementation leads to overlapping subproblems and higher time complexity.
This recursive solution is easy to implement but inefficient for larger n due to exponential time complexity.
This C program defines a recursive function 'fibonacci' which returns the nth Fibonacci number by recursively calling itself with (n-1) and (n-2) until reaching the base cases of 0 or 1.
Complexity
Time Complexity: O(2^n) because it grows exponentially, with overlapping subproblems.
Space Complexity: O(n) due to the recursion stack required by function calls.
Approach 2: Dynamic Programming Approach
The dynamic programming approach involves using an array to store previously computed Fibonacci numbers, which prevents redundant calculations found in the recursive approach. This method significantly improves efficiency by transforming the exponential recursive solution into a linear solution, using merely linear space.
In this C solution, an array 'fib' is used to store Fibonacci numbers up to n. The base cases are initialized, and the array is filled iteratively, computing each Fibonacci number from the two preceding numbers, achieving a linear time complexity.
Complexity
Time Complexity: O(n) due to linear iteration.
Space Complexity: O(n) for the array storing Fibonacci numbers.
Approach 3: Recurrence
We define two variables a and b, initially a = 0 and b = 1.
Next, we perform n iterations. In each iteration, we update the values of a and b to b and a + b, respectively.
Finally, we return a.
The time complexity is O(n), where n is the given integer. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Approach 4: Matrix Exponentiation
We define Fib(n) as a 1 times 2 matrix \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}, where F_n and F_{n - 1} are the n-th and (n - 1)-th Fibonacci numbers, respectively.
We want to derive Fib(n) from Fib(n - 1) = \begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix}. In other words, we need a matrix base such that Fib(n - 1) times base = Fib(n), i.e.:
$
\begin{bmatrix}
F_{n - 1} & F_{n - 2}
\end{bmatrix} times base = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}
Since F_n = F_{n - 1} + F_{n - 2}, the first column of the matrix base is:
\begin{bmatrix}
1 \
1
\end{bmatrix}
The second column is:
\begin{bmatrix}
1 \
0
\end{bmatrix}
Thus, we have:
\begin{bmatrix} F_{n - 1} & F_{n - 2} \end{bmatrix} times \begin{bmatrix}1 & 1 \ 1 & 0\end{bmatrix} = \begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}
We define the initial matrix res = \begin{bmatrix} 1 & 0 \end{bmatrix}, then F_n is equal to the second element of the first row of the result matrix obtained by multiplying res with base^{n}. We can solve this using matrix exponentiation.
The time complexity is O(log n), and the space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(2^n) because it grows exponentially, with overlapping subproblems. Space Complexity: O(n) due to the recursion stack required by function calls. |
| Dynamic Programming Approach | Time Complexity: O(n) due to linear iteration. |
| Recurrence | — |
| Matrix Exponentiation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive (Brute Force) | O(2^n) | O(n) | Useful for demonstrating the recurrence relation and understanding recursion trees |
| Dynamic Programming (Bottom-Up) | O(n) | O(n) | Standard interview solution when computing Fibonacci iteratively |
| Memoization (Top-Down DP) | O(n) | O(n) | Good when you want recursion but avoid repeated subproblem computation |
Video Solution
Fibonacci Number | Recur + Memo | Bottom Up | DP Concepts & Qns - 2 | Leetcode-509 • codestorywithMIK • 43,143 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Fibonacci Number easy or hard?
Fibonacci Number Python/Java solution
How to solve Fibonacci Number in O(n)?
What is the best approach for Fibonacci Number?
Is Fibonacci Number asked at Google/Amazon/Meta?
What data structure is used in Fibonacci Number?
What is the time complexity of Fibonacci Number?
Ready to solve this problem?
Practice Fibonacci Number with our built-in code editor and test cases.
Practice on FleetCode