Memoization | Skilled.dev
Learn

Memoization

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

Memoization (or caching) is an optimization that stores the result from a function call or expensive calculation so that the code isn't executed more than once for the same input. Like many of our optimizations, we incur additional space to lower our time complexity.

Memoization can be applied broadly in software engineering, but in interviews, we most often see it with dynamic programming for storing the results of subproblems.

Simple Example

For functions, we always expect them to return the same result when called with the same input. With memoization, we store the result of a function call for a given input so that we can return immediately instead of recalculating the answer.

The below example is contrived but still valuable to gain the insight. Before memoizing, this function takes O(n) time because we go from 0 to n everytime we call the function.

const countByTwo = (n) => {
  let count = 0;

  for (let i = 0; i <= n; i++) {
    count = count + 2;
  }

  return count;
}

After we introduce memoization, it only takes O(n) the first time we calculate for a given input n. Then if we call the function again with n, it will return in O(1) since we already know the solution.

const memo = {};

const countByTwo = (n) => {
  // Check if we previously memoized the result and return early in O(1) time
  if (memo[n]) {
    return memo[n];
  }

  let count = 0;

  for (let i = 0; i <= n; i++) {
    count = count + 2;

    // Store the result for this value
    // It will return instantly if called later with one of these values
    memo[i] = count;
  }

  // We calculated and stored this value (and all previous values) in the for loop
  return memo[n];
}

Memoization and Dynamic Programming

In dynamic programming, we build our solution by solving subproblems with different function input values and combine the results to get our solution. We use memoization to store the result for overlapping subproblems (problems called with the same input multiple times) so that we only have to perform the calculation once.

Calculating Fibonacci numbers is a classic example for using dynamic programming and applying memoization. Without memoization, it requires ~O(2n) time complexity.

const fib = (n) => {
  if (n < 2) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

Let's take a look at what is happening if we call fib(7) without memoization. The value in the node is the input for a recursive call, and the tree represents how the recursive calls spawn additional calls, with a lot of overlap. We can see nodes with the same value many times which means they are overlapping subproblems that are being executed fully.

Credit: VisuAlgo

Not only do we call the same function many times, but each time it also triggers additional recursive calls. If we instead store the result of a function call, we can just use the memoized value that was previously calculated instead going deeper into the recursive tree.

For this problem, we use a hash table where the key is the result for calcuting a Fibonacci number which corresponds to the current input to the function.

Which looks like:

// Hash table with store results for different inputs
fibMemoHashTable = {
  0: 0, // fib(0)
  1: 1, // fib(1)
  2: 1, // fib(2)
  3: 2, // fib(3)
  4: 3, // fib(4)
  5: 5, // fib(5)
  6: 8, // fib(6)
  7: 13, // fib(7)
  // ... and so on for all the fibonacci numbers
}

Translating this to code, we get the following:

const memo = {};

const fib = (n) => {
  if (n < 2) {
    return n;
  }

  // If we have the value in our hash table,
  // return it instead of continuing with the recursive case
  if (memo[n]) {
    return memo[n];
  }

  const nthFib = fib(n - 1) + fib(n - 2);

  memo[n] = nthFib;

  return nthFib;
}

Now let's view our tree of recursive calls. The ones highlighted in blue are when we have a memoized value and would return in constant O(1) time. The white nodes are the ones that calculate the value for that input for the first time.

Credit: VisuAlgo

In face, the first time we encounter a memoized value (blue node), we immediately return the value stored an do not continue executing the recursion.

Credit: VisuAlgo

By using memoization, we improve our runtime from O(2n) to O(n). With an n of 7, this is 41 calculations vs 13, but as our input size increases, the difference increases dramatically. If we increase the input size to 25, it takes 242785 for the non-memoized version versus only 49 for the memoized version.

We can also memoize using a bottom-up approach. Again we use a hash table to store the intermediate values which will then return in O(1) time if we have a particular answer stored.

const memo = { 0: 0, 1: 1 };

function fibonacci(n) {
  if (memo[n]) {
    return memo[n];
  }

  for (let i = 2; i <= n; i++) {
    const currentFib = memo[i - 1] + memo[i - 2];
    memo[i] = currentFib;
  }

  return memo[n];
}

While using a hash table is actually not required to calculate a solution for Fibonacci bottom-up, very often in dynamic programming bottom-up solutions, you will need to construct a full table like this to solve your subproblems efficiently.

Memoization in Software Engineering

Not only do we see memoization in interviews, but it is a very common technique used in production to keep our applications running fast. Anytime we calculate something "expensive" in our application, it is common to store this result instead of needing to recalculate it every time.

  • The frontend uses memoization for UI state to prevent it from needing to re-render
  • The backend stores expensive calculations in memory
  • We cache frequent database queries in something like Redis to make the data immediately accessible
Prev
Subproblems and Overlapping Subproblems
Next
Bottom-Up vs Top-Down
Loading...

Table of Contents