Memoization in JavaScript with examples

13 Dec 2018
7 min read
Node.js
Memoization is a great technique which helps developers write more efficient code. In this post, I'll present solutions to two popular problems with the use of memoization.

Let’s start with a simple definition of memoization.

What is memoization?

Memoization is a programming technique which helps expensive operations become less expensive by storing (caching) the results of previous calculations.

What is an expensive operation?

If you take a look at the big-O chart, everything in red should be avoided, if possible.

I wrote a post on the big-O notation, so I’m not going to go into details here. Basically, big-O (or time complexity) shows the running time of an algorithm.

The more calculation a function needs to do in order to complete its task, the more expensive (and time and resource consuming) the operation is.

The classic example is the calculation of Fibonacci numbers, which usually happens with recursion, i.e. a function calls itself for a number of times to calculate the next member of the sequence.

In the Fibonacci-example above, the time complexity is horrible (O(2n)), and if you ever tried to submit a solution similar to this to Hackerrank or freeCodeCamp, you noticed that these platforms wouldn’t accept it, although the algorithms returns the correct result. Instead, they want you to think about less expensive solutions, which may be more complex in terms of code quantity, but take less time to run.

Examples

Storing the result of the previous calculation helps decrease time complexity, which means that the algorithm becomes more efficient (and your solution will pass the tests).

Let’s see how memoization works by looking at two examples.

Find factorials

The task is the following: Calculate the factorial of a given number.

Factorial is when we multiply the positive whole numbers together from 1 to the given number. The notation of the factorial is the ! (exclamation mark). For example, 5! = 120, because 1 * 2 * 3 * 4 * 5 = 120.

The function will be called findFactorial and will accept an argument, the number we want to calculate the factorial of.

The code can look like this:

function findFactorial(num) {
  if (num < 0) return 'Please enter a non-negative number.'
  if (!Number.isInteger(num)) return 'Please enter an integer.'
  if (num === 0) return 1;

  let factorial = 1;
  let i = 1;
  while (i <= num) {
    factorial *= i;
    i++;
  }

  return factorial;
}

Let’s go over it step-by-step.

First, we can do some validation. Factorials only make sense for positive whole numbers, so we can return the relevant messages if the input is other than that. For the input of zero, we’ll return 1, because 0! = 1 by convention.

The interesting part is the factorial variable, which has an initial value of 1. We’ll store the results of previous calculations in this variable.

The while statement does the lion share of the work. The value of i is increased (i++) after each multiplication until it becomes greater than num, which is our input.

For each iteration, we perform a multiplication, where the already stored product of numbers (factorial) is multiplied by the next i value.

This solution is simple and findFactorial is a pure function, meaning that its output only depends on the input and it has no side effects. If num is changed, the return value of findFactorial will also change.

This algorithm has a time complexity of O(n) (because of the iteration) and this is OK.

Find the n-th Fibonacci number

The classic Fibonacci-solution involves recursion, but we can do better here.

The task is to find the greatest Fibonacci-number that is not greater than a given upper limit.

We can create the next term of the Fibonacci-sequence by adding the two previous terms together. The first and second terms are 1 and 1. The third term (F3) is 2 (1 + 1), then 3, 5, 8, 13, 21, 34, and so on. The terms (members) of the Fibonacci-sequence are called Fibonacci numbers.

Our function can be called findFib and it’ll have one argument, which is the upper limit (num).

In the factorial example, we stored the already calculated product in a variable (factorial) of number type.

In case of findFib, we’ll need to add two numbers and one of these numbers will be different in each addition. A single variable won’t be enough here, so it might be a good idea to store the temporary results in an array.

As we go along and calculate the next Fibonacci number, we can insert the new numbers to the array by adding the last two elements.

The code can look like this:

function findFib(num) {
  if (num <= 0) return 'Please enter a positive number';
  if (num === 1) return 1;

  const fibs = [1, 1];
  let nextFib = 0;

  while ((nextFib = fibs[0] + fibs[1]) <= num) {
    fibs.unshift(nextFib);
  }

  return fibs[0];
}

We can do a simple validation first. Fibonacci numbers are positive integers, so it doesn’t make sense to have a negative upper limit. If num is 1, we can return 1 because both the first and second Fibonacci numbers are equal to 1, so 1 meets the condition of not being greater than the upper limit.

The fibs array will store the already calculated Fibonacci numbers. The first two terms of the sequence are always defined, otherwise we couldn’t move on to the next member. We need to list them as the first two elements of the array (1 and 1).

It’s shocking but nextFib will be the next Fibonacci number in the sequence. Because it’s always recalculated, we’ll need to declare it with the let keyword.

The engine of the function is - again - the while statement.

The new Fibonacci number will be inserted to the beginning of the array, because it’ll be easier to calculate the next term this way. If we pushed the new element to the end of the fibs array, we would need to mess with the length. No big deal, it’s doable, but it’s probably a bit easier and cleaner to do it this way.

We can use the unshift array method to add elements to the beginning of the array. It mutates fibs, but it’s not an issue here, because fibs need to continually change so that we can calculate the next term.

In the condition of the while statement, we add the first and the second elements of fibs (which are the largest and the second largest Fibonacci numbers before the next term is calculated), thanks to the unshift method. We’ll keep adding the first two elements until we reach the upper limit (num).

Finally, the first element of the array is returned.

With this, we could reduce the original O(2n) complexity with the recursion to O(n).

Bonus: sum of the first n Fibonacci numbers

We can also add up the Fibonacci numbers up to the upper limit.

Because the numbers are stored in an array, we can use the reduce method to add the numbers together.

Let’s rename the function to sumOfFibs, and the new, modified function looks like this:

function sumOfFibs(num) {
  if (num <= 0) return 'Input must be a positive number';
  if (num === 1) return 1;

  const fibs = [1, 1];
  let nextFib = 0;

  while ((nextFib = fibs[0] + fibs[1]) <= num) {
    fibs.unshift(nextFib);
  }

  return fibs.reduce((acc, val) => {
    return acc + val;
  }, 0);
}

The initial value is 0 and we keep adding up the numbers until we get to the end of the array.

Conclusion

As we have seen, the key is that we store (cache) the already calculated values, so that they don’t need to be recalculated later on. The hardest part is to find the best way to store the values.

I hope this post was useful. If so, see you next time.

Previous post
Next post