Log inSign up
easyLeetCodeNot Started

Fibonacci Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why naive recursion results in an exponential call tree.
  • Demonstrate the progression from recursion -> memoization -> tabulation -> rolling variables.
  • Achieve O(n) time and O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequence where next term depends purely on sum of prior two terms.
  • Archetype of overlapping subproblems.

Algorithmic Decision Tree:

  • n <= 1 -> return n directly.
  • n > 1 -> roll two variables.

Connected Patterns:

Climbing StairsN-th Tribonacci NumberHouse Robber

1. Naive Recursion

Intuition

Directly apply F(n) = F(n-1) + F(n-2) recursively.

Algorithm

  1. Define fib(n).
  2. If n <= 1, return n.
  3. Return fib(n - 1) + fib(n - 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int fibRec(int n) {
6 if (n <= 1) return n;
7 return fibRec(n - 1) + fibRec(n - 2);
8}
9
10int main() {
11 int n = 4;
12 cout << "F(" << n << ") [Recursive]: " << fibRec(n) << endl;
13 return 0;
14}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Dynamic Programming Tabulation

Intuition

Maintain array dp of size n + 1 filled iteratively.

Algorithm

  1. If n <= 1, return n.
  2. Create array dp of size n + 1.
  3. dp[0] = 0, dp[1] = 1.
  4. For i = 2 to n: dp[i] = dp[i - 1] + dp[i - 2].
  5. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int fibTab(int n) {
7 if (n <= 1) return n;
8 vector<int> dp(n + 1);
9 dp[0] = 0;
10 dp[1] = 1;
11 for (int i = 2; i <= n; i++) {
12 dp[i] = dp[i - 1] + dp[i - 2];
13 }
14 return dp[n];
15}
16
17int main() {
18 int n = 4;
19 cout << "F(" << n << ") [Tabulation]: " << fibTab(n) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) array space

3. O(1) Space Rolling Variables

Intuition

Maintain two scalars prev2 and prev1 in a single pass.

Algorithm

  1. If n <= 1, return n.
  2. prev2 = 0, prev1 = 1.
  3. For i = 2 to n:
  4. curr = prev1 + prev2
  5. prev2 = prev1
  6. prev1 = curr
  7. Return prev1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int fibOptimal(int n) {
6 if (n <= 1) return n;
7 int prev2 = 0, prev1 = 1;
8
9 for (int i = 2; i <= n; i++) {
10 int curr = prev1 + prev2;
11 prev2 = prev1;
12 prev1 = curr;
13 }
14 return prev1;
15}
16
17int main() {
18 int n = 4;
19 cout << "F(" << n << ") [Optimal O(1)]: " << fibOptimal(n) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(n)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive RecursionO(2^n)O(n)fib(n-1) + fib(n-2) recursion tree.Redundant subtrees
2.DP TabulationO(n)O(n)Array storing computed values up to n.Array memory
3.Rolling VariablesOptimalO(n)O(1)Maintain prev2 and prev1 scalars.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting n = 0 is 0 (confusing 0-indexed with 1-indexed Fibonacci).

Pitfall 2:

Using recursion without memoization.

Crucial Edge Cases to Validate:

  • n = 0: Output is 0.
  • n = 1: Output is 1.
  • n = 30: Fits comfortably within standard 32-bit signed integer.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Use Fibonacci to clearly explain the concepts of overlapping subproblems and optimal substructure.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the theoretical time complexity of computing F(n) using 2x2 matrix exponentiation?

Back to DSA Sheet