Memoize solution and explanation
Google
9 more videos on this problem
Memoize - Leetcode 2623 - JavaScript 30-Day ChallengeNeetCodeIO · 8:28 · 18K views
Memoize | Leetcode 2623 | Cache in JavaScript | 30 Days of JavaScript #leetcode #javascriptLearn With Chirag · 13:49 · 4K views
Leetcode Javascript - 2623. MemoizeAnshulOnTech · 13:31 · 1K views
#day11 | 2623. Memoize | Medium | 30 Days of Javascript | Leetcode-2623 | 30 Days Challenge JSCoding with Ankita · 13:13 · 1K views
2623. Memoize - Leetcode JavaScript Solution with ExplanationEndeavour Monk · 10:45 · 1K views
Day 9 | 30-Day JavaScript Coding Challenge on LeetCode: Memoize (Problem 2623)vanAmsen · 5:19 · 393 views
Memoize - LeetCode 2623 - JavaScript - JS 30 Day Challenge Day 9Alpha-Code · 6:41 · 228 views
2623. Memoize - Day 9/30 Leetcode Javascript ChallengeProgramming Live with Larry · 7:04 · 208 views
2623. Memoize - Leetcode (Medium). 30 Days of JavaScript | День 11 | Мемоизация и кэш в функцияхdev tsx · 5:01 · 177 views
Day 9 - 2623. MemoizeCode Crusaders · 4:27 · 122 views
The problem
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.
You can assume there are 3 possible input functions: sum, fib, and factorial.
sumaccepts two integersaandband returnsa + b. Assume that if a value has already been cached for the arguments(b, a)wherea != b, it cannot be used for the arguments(a, b). For example, if the arguments are(3, 2)and(2, 3), two separate calls should be made.fibaccepts a single integernand returns1ifn <= 1orfib(n - 1) + fib(n - 2)otherwise.factorialaccepts a single integernand returns1ifn <= 1orfactorial(n - 1) * notherwise.
Example 1:
Input: fnName = "sum" actions = ["call","call","getCallCount","call","getCallCount"] values = [[2,2],[2,2],[],[1,2],[]] Output: [4,4,1,3,2] Explanation: const sum = (a, b) => a + b; const memoizedSum = memoize(sum); memoizedSum(2, 2); // "call" - returns 4. sum() was called as (2, 2) was not seen before. memoizedSum(2, 2); // "call" - returns 4. However sum() was not called because the same inputs were seen before. // "getCallCount" - total call count: 1 memoizedSum(1, 2); // "call" - returns 3. sum() was called as (1, 2) was not seen before. // "getCallCount" - total call count: 2
Example 2:
Input: fnName = "factorial" actions = ["call","call","call","getCallCount","call","getCallCount"] values = [[2],[3],[2],[],[3],[]] Output: [2,6,2,2,6,2] Explanation: const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1)); const memoFactorial = memoize(factorial); memoFactorial(2); // "call" - returns 2. memoFactorial(3); // "call" - returns 6. memoFactorial(2); // "call" - returns 2. However factorial was not called because 2 was seen before. // "getCallCount" - total call count: 2 memoFactorial(3); // "call" - returns 6. However factorial was not called because 3 was seen before. // "getCallCount" - total call count: 2
Example 3:
Input: fnName = "fib" actions = ["call","getCallCount"] values = [[5],[]] Output: [8,1] Explanation: fib(5) = 8 // "call" // "getCallCount" - total call count: 1
Constraints:
0 <= a, b <= 1051 <= n <= 101 <= actions.length <= 105actions.length === values.lengthactions[i]is one of "call" and "getCallCount"fnNameis one of "sum", "factorial" and "fib"
Approach overview
Problem Overview: Design a memoize function that wraps another function and caches results for previously seen inputs. When the memoized function is called again with the same arguments, it should return the cached result instead of recomputing it.
Approach 1: Using a Simple Map for Caching (Average O(1) time, O(n) space)
This approach stores previously computed results inside a hash map (or Map/HashMap). Each function call generates a key representing the arguments, typically by converting the argument list into a string. When the memoized function runs, you first perform a hash lookup to check whether the key already exists. If it does, return the cached value immediately; otherwise compute the result, store it in the map, and return it. This approach works well in JavaScript, Python, and Java where dictionary-like structures provide average O(1) lookup and insertion. The total space grows to O(n) where n is the number of unique input combinations.
Approach 2: Storing Inputs as Hashable Tuples (Average O(1) time, O(n) space)
Instead of serializing arguments into a string, store them directly as a hashable tuple. Languages like Python and C# allow tuples to be used as dictionary keys because they implement hashing based on their contents. Each function call creates a tuple of the arguments and performs a dictionary lookup. If the tuple already exists, return the stored value; otherwise evaluate the original function and cache the result. This avoids the overhead and potential collisions of string serialization while keeping constant-time lookups. The dictionary still grows proportionally with unique argument combinations, so space complexity remains O(n).
Recommended for interviews: The expected solution uses a hash-based cache with constant-time lookup. Interviewers want to see that you recognize memoization as a caching technique built on top of a hash map. A straightforward map-based implementation demonstrates understanding of function wrappers and argument handling. The tuple-key approach is cleaner in languages that support hashable composite keys and often appears in discussions of dynamic programming and caching optimizations.
Approach 1: Approach 1: Using a Simple Map for Caching
In this approach, we can utilize a dictionary (or map) to cache the results of the function calls. The keys in this dictionary will be the string representation of the input arguments, and the values will be the corresponding function output. We will also maintain a count of how many unique calls have been made with new inputs.
class Memoize:
def __init__(self, func):
self.func = func
self.cache = {}
self.call_count = 0
def __call__(self, *args):
if args in self.cache:
return self.cache[args]
else:
result = self.func(*args)
self.cache[args] = result
self.call_count += 1
return result
def getCallCount(self):
return self.call_count
def sum(a, b):
return a + b
def fib(n):
if n <= 1:
return 1
return fib(n - 1) + fib(n - 2)
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)import java.util.HashMap;
import java.util.Map;
class Memoize<T, R> {
private final Map<T, R> cache = new HashMap<>();
private int callCount = 0;
private final Function<T, R> func;
public Memoize(Function<T, R> func) {
this.func = func;
}
public R apply(T args) {
if (cache.containsKey(args)) {
return cache.get(args);
}
R result = func.apply(args);
cache.put(args, result);
callCount++;
return result;
}
public int getCallCount() {
return callCount;
}
}
interface Function<T, R> {
R apply(T t);
}
// Example usages
Function<int[], Integer> sum = (int[] args) -> args[0] + args[1];
Function<Integer, Integer> fib = (n) -> (n <= 1) ? 1 : fib.apply(n - 1) + fib.apply(n - 2);
Function<Integer, Integer> factorial = (n) -> (n <= 1) ? 1 : n * factorial.apply(n - 1);function memoize(fn) {
const cache = {};
let callCount = 0;
return function(...args) {
const key = JSON.stringify(args);
if (cache[key] !== undefined) {
return cache[key];
} else {
const result = fn(...args);
cache[key] = result;
callCount++;
return result;
}
};
memoize.getCallCount = function() {
return callCount;
};
}
function sum(a, b) {
return a + b;
}
function fib(n) {
if (n <= 1) return 1;
return fib(n - 1) + fib(n - 2);
}
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}The Memoize class is defined to wrap the target function. It maintains a cache dictionary and a call count integer. If the input arguments are already present in the cache, the cached result is returned. Otherwise, the function is called, the result is cached, and the call count is incremented.
The time complexity for each call is O(1) due to dictionary lookups. The space complexity is O(n) in the worst case, where n is the number of unique calls made, due to storage in the cache.
Approach 2: Approach 2: Storing Inputs as Hashable Tuples
Preserving the order and distinction of each argument set is crucial and can be achieved using tuples for arguments. With languages like Python, tuples can directly represent immutable and hashable keys for our cache. Similar adaptations exist for other languages, respecting each language's constraints around tuple-like structures and hashable types.
class Memoize:
def __init__(self, func):
self.func = func
self.cache = {}
self.call_count = 0
def __call__(self, *args):
key = tuple(args)
if key in self.cache:
return self.cache[key]
else:
result = self.func(*args)
self.cache[key] = result
self.call_count += 1
return result
def getCallCount(self):
return self.call_countusing System;
using System.Collections.Generic;
public class Memoize<TArgs, TResult>
{
private readonly Func<TArgs, TResult> _func;
private readonly Dictionary<TArgs, TResult> _cache;
private int _callCount;
public Memoize(Func<TArgs, TResult> func)
{
_func = func;
_cache = new Dictionary<TArgs, TResult>();
_callCount = 0;
}
public TResult Call(TArgs args)
{
if (_cache.TryGetValue(args, out TResult result))
{
return result;
}
result = _func(args);
_cache[args] = result;
_callCount++;
return result;
}
public int GetCallCount() => _callCount;
}
public static class Program
{
public static int Sum((int, int) args) => args.Item1 + args.Item2;
public static int Fib(int n) => n <= 1 ? 1 : Fib(n - 1) + Fib(n - 2);
public static int Factorial(int n) => n <= 1 ? 1 : n * Factorial(n - 1);
}This approach defines the key for cache lookups as a tuple of the input arguments, leveraging Python's native tuple hashability to allow efficient cache operations.
O(1) lookup time in the cache; Space complexity is O(n), dependent on the number of distinct calls stored.
Approach 3: Default Approach
type Fn = (...params: any) => any;
function memoize(fn: Fn): Fn {
const cache: Record<any, any> = {};
return function (...args) {
if (args in cache) {
return cache[args];
}
const result = fn(...args);
cache[args] = result;
return result;
};
}
/**
* let callCount = 0;
* const memoizedFn = memoize(function (a, b) {
* callCount += 1;
* return a + b;
* })
* memoizedFn(2, 3) // 5
* memoizedFn(2, 3) // 5
* console.log(callCount) // 1
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Simple Map for Caching | The time complexity for each call is O(1) due to dictionary lookups. The space complexity is O(n) in the worst case, where n is the number of unique calls made, due to storage in the cache. |
| Approach 2: Storing Inputs as Hashable Tuples | O(1) lookup time in the cache; Space complexity is O(n), dependent on the number of distinct calls stored. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Map Caching | O(1) average per call | O(n) | General-purpose memoization when arguments can be serialized into a unique key |
| Hashable Tuple Keys | O(1) average per call | O(n) | Languages with native tuple hashing like Python or C#, avoids string serialization overhead |
Frequently asked questions
Is Memoize easy or hard?
Memoize is usually considered a medium difficulty problem. The implementation itself is straightforward, but handling function arguments, building reliable cache keys, and understanding the concept of memoization require solid knowledge of hash maps and higher-order functions.
Memoize Python/Java solution
In Python, memoization typically uses a dictionary where the key is a tuple of function arguments. In Java, a HashMap stores argument representations as keys and computed values as entries. JavaScript commonly uses a Map with serialized argument arrays as keys.
How to solve Memoize in O(1)?
Use a dictionary or hash map to store results keyed by the function arguments. On every call, convert the arguments into a key (either a serialized string or a tuple) and check if it exists in the cache. If it exists, return the stored value; otherwise compute the result and store it. Hash map lookups provide O(1) average-time performance.
What is the best approach for Memoize?
The best approach uses a hash map (or dictionary) to cache previously computed results. Each unique set of arguments becomes a key, and the computed result is stored as the value. Future calls perform an O(1) average-time lookup instead of recomputing the function. This approach is efficient and matches how memoization is implemented in most real systems.
Is Memoize asked at Google/Amazon/Meta?
Memoization and caching patterns appear frequently in interviews at large tech companies including Google, Amazon, and Meta. While the exact problem may vary, candidates are expected to understand how to cache function results using hash maps and how memoization optimizes repeated computations in dynamic programming.
What data structure is used in Memoize?
The core data structure is a hash map (dictionary, Map, or HashMap depending on the language). It stores a mapping between input arguments and the computed result. This structure allows constant-time average lookup and insertion, which makes memoization efficient.
What is the time complexity of Memoize?
Each call to the memoized function runs in O(1) average time because it performs a hash map lookup to check whether the result already exists. If the input combination has not been seen before, the underlying function executes once and the result is cached. Space complexity is O(n) for storing results of n unique input combinations.