Given a function fn, return a memoized version of that function.
A memoized function is a function that will never be called twice with the same inputs. Instead it will return a cached value.
fn can be any function and there are no constraints on what type of values it accepts. Inputs are considered identical if they are === to each other.
Example 1:
Input:
getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b) { return a + b; }
Output: [{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]
Explanation:
const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
For the inputs of (2, 2): 2 + 2 = 4, and it required a call to fn().
For the inputs of (2, 2): 2 + 2 = 4, but those inputs were seen before so no call to fn() was required.
For the inputs of (1, 2): 1 + 2 = 3, and it required another call to fn() for a total of 2.
Example 2:
Input:
getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b) { return ({...a, ...b}); }
Output: [{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]
Explanation:
Merging two empty objects will always result in an empty object. It may seem like there should only be 1 call to fn() because of cache-hits, however none of those objects are === to each other.
Example 3:
Input:
getInputs = () => { const o = {}; return [[o,o],[o,o],[o,o]]; }
fn = function (a, b) { return ({...a, ...b}); }
Output: [{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]
Explanation:
Merging two empty objects will always result in an empty object. The 2nd and 3rd third function calls result in a cache-hit. This is because every object passed in is identical.
Constraints:
1 <= inputs.length <= 1050 <= inputs.flat().length <= 105inputs[i][j] != NaNThis approach utilizes a hash (or map) to store computed results of the function, where the keys are generated based on the input parameters. By serializing the inputs into a unique key (e.g., using JSON), we can easily check whether a computation for the same inputs has been already done and retrieve the result from the cache if it has.
This Python solution uses a tuple of the arguments to uniquely identify each call to the function. The tuple is used as a key in a dictionary (hash map) to store results. If the inputs are repeated, the stored result is returned instead of calling the function again.
JavaScript
The time complexity of this solution is O(1) on average for each call due to hash map lookups. The space complexity is O(n) where n is the number of unique input sets to the function.
This approach is similar to hash-based memoization but emphasizes generating a custom key for complex input types that might not be directly hashable. This is particularly useful for composite objects or nested data structures where default serialization (as in JSON) is inadequate or inefficient.
The Java example uses a List to capture arguments, which makes it feasible to handle object arrays. This List is used as a key in a HashMap to store the function results, providing efficient lookup.
C++
The time complexity is O(1) on average for cache operations, assuming good hashCode implementations for objects. Space complexity is O(n) depending on unique input sets.
| Approach | Complexity |
|---|---|
| Hash-Based Memoization | The time complexity of this solution is O(1) on average for each call due to hash map lookups. The space complexity is O(n) where n is the number of unique input sets to the function. |
| Custom Key Generation for Complex Types | The time complexity is O(1) on average for cache operations, assuming good hashCode implementations for objects. Space complexity is O(n) depending on unique input sets. |
Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10 • NeetCode • 191,940 views views
Watch 9 more video solutions →Practice Memoize II with our built-in code editor and test cases.
Practice on FleetCode