Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Fibonacci Number

EASYProblemSolveExternal Links

Description

The Fibonacci numbers form a sequence where each number is the sum of the two numbers that come before it. The sequence starts with 0 and 1, and every subsequent number is built by adding the previous two together.

Formally:

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

The first several Fibonacci numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Given a non-negative integer n, compute F(n).

Examples

Example 1

Input: n = 2

Output: 1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1. The second Fibonacci number is obtained by adding the two base values.

Example 2

Input: n = 3

Output: 2

Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2. We first need F(2) = 1, then add F(1) = 1 to get 2.

Example 3

Input: n = 4

Output: 3

Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3. Each Fibonacci number depends on the two values that precede it.

Example 4

Input: n = 0

Output: 0

Explanation: F(0) = 0 is a base case defined directly. No computation is needed.

Constraints

  • 0 ≤ n ≤ 30

Editorial

Brute Force

Intuition

The definition of Fibonacci numbers is inherently recursive: F(n) = F(n-1) + F(n-2). The most natural approach is to translate this mathematical definition directly into code.

If n is 0 or 1, we return n itself (the base cases). Otherwise, we make two recursive calls — one for F(n-1) and one for F(n-2) — and return their sum.

Imagine you are asked to find the number of ancestors in your family tree at a certain generation. To answer, you need to count ancestors from each of your two parents separately, and those parents in turn need to ask their parents. The questions keep branching until you reach the founding members of the family. This branching is exactly what naive recursion does — and it repeats a lot of work because both branches ask overlapping questions.

Step-by-Step Explanation

Let's trace through computing F(5):

Step 1: Call fib(5). Since 5 > 1, we need fib(4) + fib(3).

Step 2: Call fib(4). Since 4 > 1, we need fib(3) + fib(2).

Step 3: Call fib(3) (from fib(4)'s left branch). Since 3 > 1, we need fib(2) + fib(1).

Step 4: Call fib(2) (from fib(3)'s left branch). Since 2 > 1, we need fib(1) + fib(0).

Step 5: Call fib(1). Base case: return 1.

Step 6: Call fib(0). Base case: return 0.

Step 7: fib(2) = fib(1) + fib(0) = 1 + 0 = 1. Resolved.

Step 8: Call fib(1) (from fib(3)'s right branch). Base case: return 1.

Step 9: fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Resolved.

Step 10: Call fib(2) (from fib(4)'s right branch). This is a REPEATED computation — fib(2) was already calculated in Step 7!

  • fib(2) = fib(1) + fib(0) = 1 + 0 = 1.

Step 11: fib(4) = fib(3) + fib(2) = 2 + 1 = 3. Resolved.

Step 12: Now compute fib(3) (from fib(5)'s right branch). This is ALSO repeated — fib(3) was already computed in Step 9!

  • fib(3) = fib(2) + fib(1) = 1 + 1 = 2.

Step 13: fib(5) = fib(4) + fib(3) = 3 + 2 = 5.

Result: F(5) = 5

Notice how fib(2) was computed 3 times and fib(3) was computed 2 times. This redundancy is the core inefficiency.

Naive Recursion — Exponential Call Tree for F(5) — Watch how the recursion branches into an exponential tree of calls, with many subproblems being recomputed multiple times.

Algorithm

  1. If n ≤ 1, return n (base cases: F(0) = 0, F(1) = 1)
  2. Otherwise, return fib(n-1) + fib(n-2)
  3. Each call branches into two recursive calls until reaching the base cases

Code

class Solution {
public:
    int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
};
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        return self.fib(n - 1) + self.fib(n - 2)
class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

Each call spawns two more calls, creating a binary tree of calls. The total number of nodes in this tree roughly doubles at each level, leading to exponential growth. For fib(5) alone, we make around 15 calls. For fib(30), this balloons to over a billion.

Space Complexity: O(n)

The recursion goes at most n levels deep before hitting a base case. At any point, only one path from root to leaf exists on the call stack. The maximum stack depth is n, so the space usage is O(n).

Why This Approach Is Not Efficient

The naive recursion has O(2^n) time complexity because it recomputes the same subproblems over and over. When computing fib(5), the subproblem fib(2) is solved 3 times and fib(3) is solved 2 times. For larger values of n, this redundancy grows explosively.

With n up to 30 in our constraints, the naive approach would make roughly 2^30 ≈ 10^9 function calls — far too slow for any reasonable time limit.

The root cause is that the recursion tree contains overlapping subproblems: multiple branches of the tree ask the same question independently. If we could remember (memoize) the answer to each subproblem the first time we solve it, we would never need to recompute it. This is the foundation of dynamic programming.

Better Approach - Memoized Recursion

Intuition

The key observation is that the naive recursion repeatedly solves the same subproblems. We can fix this by storing (memoizing) each result the first time we compute it. Before making any recursive call, we check if the answer is already saved. If it is, we return it immediately instead of recursing.

This technique is called top-down dynamic programming or memoization. It preserves the natural recursive structure of the solution but eliminates all redundant work. Each unique subproblem is solved exactly once.

Think of it as keeping a notebook during an exam. The first time you solve a subproblem, you write the answer in your notebook. The next time the same question comes up, you look it up instead of rederiving it from scratch.

Step-by-Step Explanation

Let's trace through computing F(5) with memoization:

Step 1: Call fib(5). Not in memo. Recurse for fib(4) and fib(3).

Step 2: Call fib(4). Not in memo. Recurse for fib(3) and fib(2).

Step 3: Call fib(3). Not in memo. Recurse for fib(2) and fib(1).

Step 4: Call fib(2). Not in memo. Recurse for fib(1) and fib(0).

Step 5: fib(1) = 1 (base case). fib(0) = 0 (base case).

Step 6: fib(2) = 1 + 0 = 1. Store memo[2] = 1.

Step 7: fib(1) = 1 (base case). fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Store memo[3] = 2.

Step 8: fib(2) is requested by fib(4) — FOUND in memo! Return 1 instantly. No recursion needed.

Step 9: fib(4) = fib(3) + fib(2) = 2 + 1 = 3. Store memo[4] = 3.

Step 10: fib(3) is requested by fib(5) — FOUND in memo! Return 2 instantly.

Step 11: fib(5) = fib(4) + fib(3) = 3 + 2 = 5. Store memo[5] = 5.

Result: F(5) = 5, computed with only 9 calls instead of ~15.

Memoized Recursion — Pruning Redundant Branches — Watch how memoization eliminates repeated computations. When a subproblem is requested a second time, we retrieve the cached result instantly instead of recursing.

Algorithm

  1. Create a memo array of size n+1, initialized to -1 (meaning "not yet computed")
  2. Define a helper function fib(n, memo):
    a. If n ≤ 1, return n (base case)
    b. If memo[n] ≠ -1, return memo[n] (already computed)
    c. Compute memo[n] = fib(n-1, memo) + fib(n-2, memo)
    d. Return memo[n]
  3. Call the helper with the initial n

Code

class Solution {
public:
    int fibHelper(int n, vector<int>& memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }
    
    int fib(int n) {
        vector<int> memo(n + 1, -1);
        return fibHelper(n, memo);
    }
};
class Solution:
    def fib(self, n: int) -> int:
        memo = [-1] * (n + 1)
        
        def fib_helper(k: int) -> int:
            if k <= 1:
                return k
            if memo[k] != -1:
                return memo[k]
            memo[k] = fib_helper(k - 1) + fib_helper(k - 2)
            return memo[k]
        
        return fib_helper(n)
class Solution {
    private int fibHelper(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
        return memo[n];
    }
    
    public int fib(int n) {
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return fibHelper(n, memo);
    }
}

Complexity Analysis

Time Complexity: O(n)

Each unique subproblem from fib(0) to fib(n) is computed exactly once and then cached. There are n+1 unique subproblems, and each takes O(1) work (a single addition plus a memo lookup). Total: O(n).

Space Complexity: O(n)

The memo array has n+1 entries, and the recursion stack goes at most n levels deep. Both contribute O(n) space.

Why This Approach Is Not Efficient

Memoization reduces the time from O(2^n) to O(n), which is a massive improvement. However, it still uses O(n) space for both the memo table and the recursion call stack.

We can observe that the Fibonacci recurrence F(n) = F(n-1) + F(n-2) only depends on the previous two values — not on all previous values. This means we don't need to store the entire memo table. If we compute the values bottom-up (iteratively), we can build each Fibonacci number from the two before it using a simple loop, eliminating the recursion stack entirely.

Furthermore, since each step only looks at the last two results, we can reduce space to O(1) by keeping only two variables instead of an entire array.

Better Approach - Bottom-Up Dynamic Programming

Intuition

Instead of starting from fib(n) and working our way down recursively, we can start from the bottom — from fib(0) and fib(1) — and iteratively build upward.

We create a table (array) where dp[i] stores F(i). We fill in the base cases dp[0] = 0 and dp[1] = 1, then for each index from 2 to n, we compute dp[i] = dp[i-1] + dp[i-2]. When we reach dp[n], we have our answer.

This is called bottom-up dynamic programming or tabulation. It avoids recursion entirely, so there is no risk of stack overflow and no overhead from function calls.

Step-by-Step Explanation

Let's trace through computing F(5) with bottom-up DP:

Step 1: Create dp array of size 6. Set dp[0] = 0, dp[1] = 1.

  • dp = [0, 1, _, _, _, _]

Step 2: Compute dp[2] = dp[1] + dp[0] = 1 + 0 = 1.

  • dp = [0, 1, 1, _, _, _]

Step 3: Compute dp[3] = dp[2] + dp[1] = 1 + 1 = 2.

  • dp = [0, 1, 1, 2, _, _]

Step 4: Compute dp[4] = dp[3] + dp[2] = 2 + 1 = 3.

  • dp = [0, 1, 1, 2, 3, _]

Step 5: Compute dp[5] = dp[4] + dp[3] = 3 + 2 = 5.

  • dp = [0, 1, 1, 2, 3, 5]

Result: dp[5] = 5

Bottom-Up DP — Building the Fibonacci Table — Watch how we fill the DP table left to right, computing each Fibonacci number from the two values immediately before it.

Algorithm

  1. Handle base cases: if n ≤ 1, return n
  2. Create a dp array of size n+1
  3. Set dp[0] = 0, dp[1] = 1
  4. For i from 2 to n:
    • Set dp[i] = dp[i-1] + dp[i-2]
  5. Return dp[n]

Code

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop runs from 2 to n, performing one addition per iteration. Total: n-1 additions = O(n).

Space Complexity: O(n)

We allocate a dp array of size n+1 to store all intermediate Fibonacci values. However, we only ever look at the last two entries when computing the next one — an observation that leads to the optimal space solution.

Why This Approach Is Not Efficient

The bottom-up DP approach achieves O(n) time, which matches the memoized approach and is optimal for this problem. However, it still uses O(n) space for the dp array.

Looking at the recurrence dp[i] = dp[i-1] + dp[i-2], we notice that computing dp[i] only requires the two most recent values. We never look further back than two positions. This means we can replace the entire array with just two variables, reducing space from O(n) to O(1).

This space optimization is a common technique in dynamic programming whenever the recurrence depends on a fixed number of previous states.

Optimal Approach - Space-Optimized Iterative

Intuition

Since each Fibonacci number only depends on the previous two, we do not need an entire array. We can maintain just two variables — representing F(i-2) and F(i-1) — and slide them forward as we compute each new value.

After computing the current Fibonacci number as the sum of the two previous ones, we update the variables: the old F(i-1) becomes the new F(i-2), and the newly computed value becomes the new F(i-1). This rolling window of size 2 replaces the full dp table.

Think of it as climbing a staircase while only remembering the last two steps. You don't need to memorize every step you've ever taken — just the two most recent ones are enough to decide your next move.

Step-by-Step Explanation

Let's trace through computing F(5) with two variables:

Step 1: Initialize prev2 = 0 (represents F(0)), prev1 = 1 (represents F(1)).

Step 2: i = 2: curr = prev1 + prev2 = 1 + 0 = 1.

  • Update: prev2 = 1 (old prev1), prev1 = 1 (curr).
  • Now prev2 = F(1), prev1 = F(2).

Step 3: i = 3: curr = prev1 + prev2 = 1 + 1 = 2.

  • Update: prev2 = 1 (old prev1), prev1 = 2 (curr).
  • Now prev2 = F(2), prev1 = F(3).

Step 4: i = 4: curr = prev1 + prev2 = 2 + 1 = 3.

  • Update: prev2 = 2 (old prev1), prev1 = 3 (curr).
  • Now prev2 = F(3), prev1 = F(4).

Step 5: i = 5: curr = prev1 + prev2 = 3 + 2 = 5.

  • Update: prev2 = 3 (old prev1), prev1 = 5 (curr).
  • Now prev2 = F(4), prev1 = F(5).

Result: prev1 = F(5) = 5

Space-Optimized Iterative — Rolling Two Variables — Watch how just two variables slide forward through the Fibonacci sequence, computing each new value from the previous two without needing a full array.

Algorithm

  1. If n ≤ 1, return n directly
  2. Initialize prev2 = 0 (F(0)) and prev1 = 1 (F(1))
  3. For i from 2 to n:
    a. Compute curr = prev1 + prev2
    b. Set prev2 = prev1
    c. Set prev1 = curr
  4. Return prev1 (which now holds F(n))

Code

class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        
        int prev2 = 0;
        int prev1 = 1;
        
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        
        prev2 = 0
        prev1 = 1
        
        for i in range(2, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        
        return prev1
class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        
        int prev2 = 0;
        int prev1 = 1;
        
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop iterates from 2 to n, performing a constant number of additions and assignments per iteration. Total: n-1 iterations = O(n). This is optimal because we must examine all n Fibonacci numbers in order to compute the nth one.

Space Complexity: O(1)

We use only three integer variables (prev2, prev1, curr) regardless of the value of n. No arrays, no recursion stack, no hash maps — constant space.