Mastering Memoization in JavaScript: Advanced Techniques with 10 Examples

Diving into the ever-evolving realm of JavaScript optimization, there’s a standout technique that’s like a turbocharger for your code: memoization. Furthermore, sometimes it is called Javascript Memoize. This powerhouse approach involves storing the outcomes of demanding function calls and then using these cached results whenever you encounter the same inputs again. The result? A remarkable performance boost. Thus, buckle up as we embark on a journey to uncover the inner workings of memoization, its extensive array of advantages, and a comprehensive exploration of 10 complicated examples that truly highlight its incredible capabilities.

Unraveling the Mysteries of Memoization Imagine grappling with a knotty function, only to realize you’re summoning it over and over again with identical arguments. Enter memoization, swooping in to rescue you by preserving those computations and serving up instant outcomes. This not only wipes out redundant toil but also injects a hefty dose of efficiency into your application’s veins.

Don’t hesitate to use powerful tools for Javascript Memoization

Memoization can be harnessed through diverse strategies, spanning from closures to objects, and even leveraging powerful libraries like Lodash. While basic memoization gets the job done for straightforward tasks, achieving mastery in the realm of intricate scenarios demands a firm grip on how to navigate a plethora of challenges.

1. Fibonacci with Memoization

This example demonstrates how to optimize the calculation of Fibonacci numbers using memoization. The memoizedFibonacci function returns a memoized version of the Fibonacci function. It uses a cache to store previously computed Fibonacci values and returns cached values if available, avoiding redundant calculations.

2. Matrix Chain Multiplication

The matrixChainOrder function tackles the problem of finding the optimal way to parenthesize matrix multiplication for the least number of operations. It uses memoization with the cache array to store calculated results for subproblems, which greatly reduces the number of redundant calculations.

3. Longest Common Subsequence

Imagine that you’re in a scenario resembling a senior JavaScript developer interview. Imagine being prompted to solve a particular problem. Of course, we’ll eventually examine the solution, but for now, let’s attempt to work through it independently. Just like in a real interview setting, we’ll take a crack at solving the problem on our own before we review the solution.

— — — — —

You are given two strings, str1 and str2. Write a function, longestCommonSubsequence, which returns the length of the longest common subsequence between these two strings and also provides the actual subsequence.

Implement the function using memoization to optimize the solution and avoid redundant calculations. The memoization cache should store the lengths of common subsequences for various indices in both strings.

Provide your solution along with an example that demonstrates the function’s correctness using the input:

• str1 = "AGGTAB"
• str2 = "GXTXAYB"

What is the length of the longest common subsequence between these two strings? Additionally, provide the actual longest common subsequence. Explain your approach and how memoization helps enhance the efficiency of the algorithm.

Expected Output:

The length of the longest common subsequence is 4.
The longest common subsequence is "GTAB".

In your response, showcase both the implementation of the longestCommonSubsequence function, including the code that prints the subsequence, and an explanation of how the memoization technique optimizes the calculation of the longest common subsequence for the given input strings.

This example focuses on finding the longest common subsequence between two strings using memoization. The longestCommonSubsequence function employs a 2D cache to store already computed subsequence lengths. By avoiding recalculations through memoization, it optimizes the process of finding the longest common subsequence.

Here’s a step-by-step breakdown of the code:

1- Function Definition: longestCommonSubsequence(str1, str2)
This is the main function that takes two input strings, str1 and str2.

2- Cache Initialization:

const cache = Array.from({ length: str1.length + 1 }, () => Array(str2.length + 1).fill(-1))

This code creates a 2D array called cache to store the computed LCS lengths. The dimensions of the array are (str1.length + 1) x (str2.length + 1). Each entry in the array is initialized with -1, which will be used to mark unfilled cells.

3- Inner Function: lcs(i, j)

This is a recursive inner function that calculates the LCS length for substrings of str1 and str2 up to indices i and j respectively.

• If either of the indices (i or j) reaches 0, the LCS length is 0 because there are no characters left to compare.
• If the value at cache[i][j] is not -1, it means the LCS length for these indices has already been calculated and stored in the cache. Return that value.
• If the characters in the current positions i - 1 in str1 and j - 1 in str2 are equal, then the LCS length increases by 1 and the recursive call is made for the previous positions: lcs(i - 1, j - 1).
• If the characters are not equal, the LCS length is the maximum of two possibilities: either excluding the character at position i from str1 (lcs(i - 1, j)) or excluding the character at the position j from str2 (lcs(i, j - 1)).
• The calculated LCS length is stored in the cache and returned.

4- Calculating the LCS Length:

const length = lcs(str1.length, str2.length)

The main function calculates the LCS length by calling the lcs function with the lengths of the entire input strings str1 and str2.

5- Constructing the LCS Subsequence:

let subsequence = ''
let i = str1.length
let j = str2.length

while (i > 0 && j > 0) {
  // ...
}

This loop constructs the LCS subsequence by iterating backward through the cache array. Starting from the last cell in the cache, it examines whether the characters at the corresponding positions in str1 and str2 are equal or not. If they are equal, the character is part of the LCS, and we move diagonally up-left in the cache. If they are not equal, we decide which direction to move based on which adjacent cell has a greater value in the cache.

6- Returning the Result:

return { length, subsequence }

The function returns an object containing the calculated LCS length (length) and the LCS subsequence (subsequence).

7- Example Usage:

const str1 = 'AGGTAB'
const str2 = 'GXTXAYB'
const { length, subsequence } = longestCommonSubsequence(str1, str2)

This code demonstrates how to use the longestCommonSubsequence function with the example strings 'AGGTAB' and 'GXTXAYB'. The resulting length will be 4 and the subsequence will be 'GTAB'.

In summary, the code uses a combination of dynamic javascript logic and backtracking to efficiently solve the Longest Common Subsequence problem and find both the length of the LCS and the actual subsequence itself.

4. Memoization with Function Composition

The composeMemoized function demonstrates how memoization can be applied to a composition of functions. It takes multiple functions as arguments and returns a new function that composes these functions while utilizing memoization to store and reuse intermediate results.

Here’s how the composeMemoized function works:

1. A cache (Map) is created to store intermediate results of composed function calls.
2. The returned function (composed) accepts arguments that are passed through the composed chain of functions.
3. Before invoking the composed chain, a unique cache key is generated based on the provided arguments.
4. If the cache contains the result associated with the key, that result is returned immediately.
5. If not, the composed chain of functions is executed using the provided arguments.
6. Intermediate results are stored in the cache to avoid redundant calculations.
7. The final result is returned and stored in the cache for future reference.

In this example, addOne and double are two simple functions. When composing them using composeMemoized, the composed function first doubles the input and then adds one to the result. The memoization ensures that if the same inputs are encountered again, the intermediate result is reused from the cache, eliminating the need for redundant calculations.

This technique is particularly useful when dealing with complex data transformations or when building a series of transformations that can benefit from memoization. It enhances both the readability and performance of your code by efficiently reusing previously calculated results.

5. Coin Change Problem

The Coin Change Problem is a classic dynamic programming problem that involves determining the minimum number of coins needed to make a certain amount. Given a set of coin denominations and an amount, the goal is to find the smallest number of coins required to make up that amount.

The coinChange function addresses the classic coin change problem using memoization. It efficiently calculates the minimum number of coins needed to make a given amount by caching subproblem results and avoiding redundant calculations.

In this code example, the coinChange function employs memoization to solve the Coin Change Problem efficiently.

1- A cache object (cache) is created to store the results of subproblems. The keys of the cache represent the remaining amounts to be achieved using the given coin denominations.

2- The dp (dynamic programming) function is defined. It takes an amount n as input and returns the minimum number of coins needed to make that amount.

3- Base cases are handled:

• If the remaining amount is 0, no coins are needed, so the function returns 0.
• If the remaining amount is negative, it's not possible to make a change, so the function returns -1.
• If the result is already present in the cache, it's returned to avoid redundant calculations.

4- For each coin denomination in the coins array, the function recursively calculates the number of coins needed to make the remaining amount after subtracting the current coin's value. The minimum of these results is considered.

5- The minimum value is stored in the cache unless no valid combination of coins is found. In that case, -1 is stored to indicate that the amount cannot be achieved using the given coins.

6- The result for the given amount is returned, which represents the minimum number of coins needed.

In the example, with the coin denominations [1, 2, 5] and the amount 11, the optimal solution is to use one coin of denomination 5 and three coins of denomination 2, resulting in a total of 3 coins. Memoization helps avoid redundant calculations for various subproblem amounts, significantly improving the efficiency of finding the minimum number of coins required.

6. Nth Tribonacci Number

This example computes the nth Tribonacci number using memoization. The tribonacci function employs a cache to store previously computed Tribonacci numbers, ensuring that each value is calculated only once.

In this example, the tribonacci function employs memoization to efficiently calculate the Nth Tribonacci number.

1. A cache object (cache) is created to store the calculated Tribonacci values. The keys of the cache represent the indices of the Tribonacci sequence.
2. The calcTribonacci function is defined. It takes an index k as input and returns the k-th Tribonacci number.
3. Base cases are handled:
   - If k is 0, return 0.
   - If k is 1 or 2, return 1.
   - If the result is already present in the cache, return it to avoid redundant calculations.

• If k is 1 or 2, return 1.
• If the result is already present in the cache, return it to avoid redundant calculations.

1. The Tribonacci value at index k is calculated by summing the three preceding Tribonacci values: calcTribonacci(k - 1) + calcTribonacci(k - 2) + calcTribonacci(k - 3).
2. The calculated value is stored in the cache to avoid recalculating it in the future.
3. The result for the requested index n is returned.

7. Palindromic Substrings Count

Given a string, you need to count the number of palindromic substrings within it.

In this example, the countPalindromicSubstrings function uses memoization to efficiently calculate the count of palindromic substrings within the given string.

1. A cache object (cache) is created using a Map to store the results of subproblem checks. The keys of the cache are substrings.
2. The isPalindrome function is defined. It takes a substring str as input and checks whether it's a palindrome.
3. Base cases are handled:
   - If the length of str is 0 or 1, it’s a palindrome (empty string or single character).
   - If the result is already present in the cache, it’s returned to avoid redundant calculations.
4. The isPalindrome function checks if the first and last characters of str are the same and recursively checks the substring without those characters.
5. The result of the palindrome check is stored in the cache to avoid recalculating it in the future.
6. The main loop iterates through all possible substrings within the input string. For each substring, it checks if it’s a palindrome using the isPalindrome function.
7. The count of palindromic substrings is updated based on whether the current substring is a palindrome.
8. The final count of palindromic substrings is returned.

In the example, calling countPalindromicSubstrings("ababa") calculates the count of palindromic substrings within the input string "ababa." The memoization technique optimizes the palindrome checks for different substrings, eliminating redundant calculations and enhancing the efficiency of counting palindromic substrings.

This approach is particularly useful when dealing with problems that involve checking properties of substrings or subarrays, as it helps avoid repetitive calculations and significantly improves performance.

8. Longest Increasing Subsequence

Given an array of integers, you’re tasked with finding the length of the longest increasing subsequence.

In this example, the longestIncreasingSubsequence function uses memoization to efficiently calculate the length of the longest increasing subsequence within the given array.

1. A cache object (cache) is created using a Map to store the results of subproblem calculations. The keys of the cache are indices in the input array.
2. The lisEndingAt function is defined. It takes an index as input and calculates the length of the longest increasing subsequence ending at that index.
3. Base case: If the index is 0, the function returns 1 (as a single element forms a valid subsequence).
4. If the result is already present in the cache, it’s returned to avoid redundant calculations.
5. The function iterates through the array elements from index 0 to the given index. For each element, it checks if it can be included in the increasing subsequence ending at the given index.
6. If the element at index i is smaller than the element at the given index, which means it can be included in the subsequence. The maximum length of subsequences ending at the index i is calculated, and the result is stored in maxLength.
7. The result of the calculation is stored in the cache to avoid recalculating it in the future.
8. The main loop iterates through all indices in the input array. For each index, it calculates the length of the longest increasing subsequence ending at that index.
9. The length of the longest increasing subsequence is updated based on the maximum length calculated for all indices.
10. The final length of the longest increasing subsequence is returned.

In the example, calling longestIncreasingSubsequence([10, 22, 9, 33, 21, 50, 41, 60, 80]) calculates the length of the longest increasing subsequence within the input array. The memoization technique optimizes the subproblem calculations, eliminating redundant calculations and enhancing the efficiency of finding the length of the longest increasing subsequence.

This approach is particularly useful when solving problems involving sequence lengths, where subproblem calculations can be reused across different indices to avoid repetitive work and significantly improve performance.

9. Matrix Chain Multiplication

The Matrix Chain Multiplication problem involves finding the optimal way to parenthesize a sequence of matrices to minimize the total number of scalar multiplications required. Given a sequence of matrices with dimensions, you need to determine the minimum number of scalar multiplications needed to compute their product.

In this example, the matrixChainOrder function uses memoization to efficiently calculate the optimal number of scalar multiplications required to multiply a sequence of matrices.

1. A cache matrix (cache) is created to store the results of subproblem calculations. The dimensions of the cache are (n x n), where n is the number of matrices in the sequence.
2. The mcm function is defined. It takes two indices i and j as input, representing the range of matrices to consider.
3. Base case: If i and j are the same, it means only one matrix is left, so no multiplication is needed (0).
4. If the result for the current range is already present in the cache, it’s returned to avoid redundant calculations.
5. The function iterates through all possible ways to split the current range into two subranges (i to k and k + 1 to j). For each split point k, the cost of parenthesizing the matrices in the subranges is calculated.
6. The cost is calculated as the sum of:
   - The cost of multiplying the matrices in the first subrange (mcm(i, k)).
   - The cost of multiplying the matrices in the second subrange (mcm(k + 1, j)).
   - The cost of multiplying the two resulting matrices (p[i — 1] * p[k] * p[j], where p is the matrix dimensions array).
7. The minimum cost among all possible split points is determined and stored in the cache for the current range.
8. The final result is the optimal number of scalar multiplications required to multiply the entire sequence of matrices (mcm(1, n - 1)).

In the example, calling matrixChainOrder([10, 30, 5, 60]) calculates the optimal number of scalar multiplications required to multiply a sequence of matrices with the given dimensions. The memoization technique optimizes the subproblem calculations, eliminating redundant calculations and enhancing the efficiency of finding the optimal number of scalar multiplications.

This approach is particularly useful for optimizing problems involving matrix multiplication, where subproblem solutions can be cached and reused to avoid repetitive calculations and significantly improve performance.

10. Longest Common Subsequence (Tabulation)

The Longest Common Subsequence (LCS) problem involves finding the length of the longest common subsequence between two sequences. Tabulation is a dynamic programming technique where you build a table iteratively to find the solution.

In this example, the longestCommonSubsequence function uses tabulation to efficiently calculate the length of the longest common subsequence between two input strings.

1. The dimensions of the tabulation table (dp) are (m + 1) x (n + 1), where m is the length of str1 and n is the length of str2.
2. The outer loop iterates through the indices of str1 (from 1 to m), and the inner loop iterates through the indices of str2 (from 1 to n).
3. For each pair of characters at the current indices (i, j):
   - If the characters match, the value at dp[i][j] is set to dp[i — 1][j — 1] + 1, as the current characters contribute to the common subsequence length.
   - If the characters don’t match, the value at dp[i][j] is set to the maximum of dp[i — 1][j] and dp[i][j — 1], as the current characters do not contribute to the common subsequence length.
4. After iterating through all possible pairs of indices, dp[m][n] holds the length of the longest common subsequence between str1 and str2.

In the example, calling longestCommonSubsequence("AGGTAB", "GXTXAYB") calculates the length of the longest common subsequence between the given strings. The tabulation technique builds the dynamic programming table iteratively, storing intermediate results and effectively finding the length of the longest common subsequence.

Tabulation is particularly useful when solving dynamic programming problems that involve building a table to keep track of intermediate solutions. It offers an efficient bottom-up approach to solving problems by iteratively filling in the table based on previously computed values.

In the example, calling tribonacci(10) calculates the 10th Tribonacci number in the sequence. The memoization technique ensures that previously calculated Tribonacci values are reused, eliminating redundant calculations and enhancing the efficiency of finding the Nth Tribonacci number.

By using memoization, the function can efficiently handle larger values of n without getting trapped in redundant calculations. This approach greatly improves the performance of solving problems related to sequence calculations.