Write a function `memoize(fn)` that returns a memoized version of `fn`. The memoized function caches results based on the argument.
Problem Statement
<p>Write a function <code>memoize(fn)</code> that returns a memoized version of <code>fn</code>. The memoized function caches results based on the argument.</p>
Examples
Input: const memo = memoize(fn); memo(5); memo(5);
Output: Returned from cache on second call
Explanation: Computation is only evaluated once.
Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Hints
š” Hint 1:
Create a cache object (Map or plain object) inside memoize.
š” Hint 2:
Before calling fn, check if the result for the given argument is already cached.
š” Hint 3:
Use a Map with JSON.stringify(args) as the key for multi-argument support.
Editorial & Approach
Problem Overview & Intuition
To solve Memoize Function, we consider the execution characteristics of JavaScript engines. Write a function `memoize(fn)` that returns a memoized version of `fn`. The memoized function caches results based on the argument. By utilizing idiomatic language constructs and clean algorithmic principles, we can accomplish this with optimal time and memory usage.
Step-by-Step Approach
- Understand Problem Contract: Identify input arguments, return type expectations, and edge cases (empty inputs, nullish values).
- Choose Core Mechanism: Use modern JavaScript patterns (create a cache object (map or plain object) inside memoize).
- Implement Logic: Handle state and transformations efficiently (before calling fn, check if the result for the given argument is already cached).
- Return Result: Ensure proper return format and preserve caller context if applicable.
Optimal Implementation (JavaScript)
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}Complexity Analysis
Time Complexity
O(1) wrapper invocation overhead
Space Complexity
O(1) closure scope retention
Edge Cases & Corner Traps Handled
- Empty or boundary inputs (empty arrays, strings, zero length).
- Type checks and unexpected values (e.g.
null,undefined, negative numbers). - Closure preservation and memory isolation between separate invocations.