Memoize - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Medium9 min readAsked at: Amazon, Microsoft, HubSpot +1

Practice this problem

Problem Statement

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.

sum accepts two integers a and b and returns a + b. Assume that if a value has already been cached for the arguments (b, a) where a != 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.
fib accepts a single integer n and returns 1 if n <= 1 or fib(n - 1) + fib(n - 2) otherwise.
factorial accepts a single integer n and returns 1 if n <= 1 or factorial(n - 1) * n otherwise.

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 <= 10⁵
1 <= n <= 10
1 <= actions.length <= 10⁵
actions.length === values.length
actions[i] is one of "call" and "getCallCount"
fnName is 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.

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.

Code

Python JavaScript Java

Python

JavaScript

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

Python C#

Python

Complexity

O(1) lookup time in the cache; Space complexity is O(n), dependent on the number of distinct calls stored.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

Try this approach in the editor →

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	—

Detailed 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

Video Solution

Memoize - Leetcode 2623 - JavaScript 30-Day Challenge • NeetCodeIO • 18,582 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Memoize with our built-in code editor and test cases.

Practice on FleetCode

Counter

Curry

Problem Info

DifficultyMedium

Acceptance63.0%

Approaches3

Reading time9 min

Asked at

Amazon Microsoft HubSpot Bloomberg

Practice this problem

Open in Editor

Memoize - Solution & Explanation

Problem Statement

Approach Overview

Approach 1: Approach 1: Using a Simple Map for Caching

Code

Complexity

Approach 2: Approach 2: Storing Inputs as Hashable Tuples

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Ready to solve this problem?

Problem Info

Table of Contents

Memoize - Solution & Explanation

Problem Statement

Approach Overview

Approach 1: Approach 1: Using a Simple Map for Caching

Code

Complexity

Approach 2: Approach 2: Storing Inputs as Hashable Tuples

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach Overview

Approach 1: Approach 1: Using a Simple Map for Caching

Code

Complexity

Approach 2: Approach 2: Storing Inputs as Hashable Tuples

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents

Problem Statement

Approach Overview

Approach 1: Approach 1: Using a Simple Map for Caching

Code

Complexity

Approach 2: Approach 2: Storing Inputs as Hashable Tuples

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents