Start learning free

LESSON 290 OF 409 · MEMOIZATION

Memoization in C++: Fibonacci in O(n) with unordered_map

Lesson O(n) Read the full explanation

In this video lesson we will learn about memoization and use it to improve the recursive fibonacci algorithm written in the previous lesson:

Problem - Fibonacci:

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.

Write a recursive function with memoization that given n, returns 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
Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 7
    Ctrl + Enter to check

    C++ · MEMOIZATION

    Memoization in C++, explained

    What memoization is

    Memoization means saving the result of a function call so that the next call with the same input returns the saved answer instead of computing it again. It works for functions that always return the same output for the same input, and it pays off when a recursive function keeps solving the same smaller problems. In C++ the saved answers usually live in an unordered_map or a vector that the recursive calls share.

    The lesson applies it to the Fibonacci numbers: F(0) = 0, F(1) = 1 and F(n) = F(n - 1) + F(n - 2) for larger n. The method fibonacci(int n) returns F(n) for 0 <= n <= 30. The examples: F(2) = 1, F(3) = 2 and F(4) = 3. The statement asks for O(n) time and O(n) extra space.

    Why plain recursion is too slow

    The direct translation of the formula calls itself twice per call:

    int fib(int n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

    It is correct, but fib(5) calls fib(3) twice, fib(2) three times, and so on. The number of calls grows about as fast as the Fibonacci numbers themselves, which is exponential. For n = 30 this version makes 2,692,537 calls to produce 832040. Almost all of them repeat work that was already done.

    Approach: compute each F(k) once

    Only 31 different values of k exist between 0 and 30. If each is computed once and remembered, the rest of the calls are map lookups. The recursion stays the same shape; a shared cache map goes in front of the recursive step. With the cache, fibonacci(30) makes 59 calls in total.

    The cache must be shared by every recursive call. The lesson does this by creating the map in fibonacci and passing it down by reference to a helper, fib.

    Step by step

    1. Declare the helper int fib(int n, unordered_map<int, int> &cache) above fibonacci. The & matters: without it, each call would receive its own copy of the map, and nothing computed deeper in the recursion would be visible to the caller.
    2. Handle the base case. If n < 2, return n, because F(0) = 0 and F(1) = 1. This also ends the recursion.
    3. Check whether n is missing from the cache with !cache[n]. The map stores 0 for a key that was just created, and 0 can only mean "not computed yet" here: every F(n) with n >= 2 is at least 1.
    4. Compute and store it. Inside the if, set cache[n] to fib(n - 1, cache) + fib(n - 2, cache). The first call, fib(n - 1, cache), fills the cache for everything below, so fib(n - 2, cache) is already stored when it runs.
    5. Return cache[n] after the if. At that point it always holds the answer, whether it was just computed or found.
    6. In fibonacci, declare an empty unordered_map<int, int> named cache.
    7. Return fib(n, cache) to start the recursion.

    The solution in C++

    class Solution {
public:
    
    int fib(int n, unordered_map<int, int> &cache) {
        if (n < 2) {
            return n;
        }
        if (!cache[n]) {
            cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
        }
        return cache[n];
    }
    int fibonacci(int n) {
        unordered_map<int, int> cache;
        return fib(n, cache);
    }
};

    Two details are worth knowing:

    • operator[] inserts. On a std::unordered_map, cache[n] for a missing key adds the key with a value of 0 and returns a reference to it. That is why !cache[n] works as a "not computed" test, and also why the test has a side effect. If 0 could be a real answer, the check would recompute it every time. A check that never inserts is cache.count(n) == 0, or cache.find(n) == cache.end().
    • Take a reference to the cache. unordered_map<int, int> &cache passes the original map. Passing it by value would copy the whole map on every call, and the copies would be thrown away, so no call would benefit from the others' work.

    Complexity

    Time: O(n). Each value from 2 to n is computed once, with one addition. Every later request for it is an average O(1) lookup. The total is about 2n calls, and for n = 30 that is 59.

    Space: O(n). The cache holds one entry per value from 2 to n, 29 entries for n = 30. The recursion goes n levels deep before the first return, so the call stack also takes O(n) space. That is harmless for n <= 30, but it is why a recursive solution with a much larger n would need a loop instead.

    Edge cases and common mistakes

    • n = 0 and n = 1. Both return n from the base case without touching the cache. The condition must be n < 2. With n < 1, F(1) would be computed as F(0) + F(-1) and come out as -1.
    • Forgetting the &. The code still compiles and returns correct values. It just has no memoization: every call works on a private copy of the map, so the running time goes back to exponential.
    • Creating the cache inside fib. A new empty map per call remembers nothing. The map has to be created once, outside the recursion.
    • Overflow for large n. int holds up to 2,147,483,647. F(46) = 1836311903 fits, but F(47) = 2971215073 does not, and signed overflow is undefined behaviour. The lesson stops at 30, well inside the range. For larger n, use long long and stop at F(92).
    • Using the cache for a value that can be 0. The !cache[n] shortcut is safe only because the base cases are handled first. In another problem, test with count or find.

    Testing

    • fibonacci(0) gives 0, and fibonacci(1) gives 1.
    • fibonacci(2) gives 1, fibonacci(3) gives 2 and fibonacci(4) gives 3.
    • fibonacci(10) gives 55.
    • fibonacci(30) gives 832040, and returns instantly. The version without a cache needs over two and a half million calls for the same input.
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free