Memoization

Interactive Visualization

1function memoize(fn) {
2  const cache = new Map();
3  return function(...args) {
4    const key = JSON.stringify(args);
5    if (cache.has(key)) {
6      return cache.get(key);  // Cache HIT
7    }
8    const result = fn(...args);
9    cache.set(key, result);
10    return result;            // Cache MISS
11  };
12}
13 
14const square = memoize(n => n * n);
15square(5);  // computes: 25
16square(5);  // cached: 25
17square(3);  // computes: 9

Key Points

• Memoization trades memory for speed - cache results for repeated calls
• Works best for pure functions (same input → same output)
• Cache key is typically derived from function arguments
• memoizeOne: caches only the last result (great for React)
• Consider cache invalidation and memory limits for production
• React.memo, useMemo, useCallback are built-in memoization

Code Examples

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;
  };
}

// Usage
const expensiveCalc = memoize((n) => {
  console.log('Computing...');
  return n * n;
});

expensiveCalc(5);  // "Computing..." → 25
expensiveCalc(5);  // → 25 (cached, no log)
expensiveCalc(10); // "Computing..." → 100

function memoize(fn, keyFn = JSON.stringify) {
  const cache = new Map();

  return function(...args) {
    const key = keyFn(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// Custom key for object arguments
const fetchUser = memoize(
  async (user) => await api.get(`/users/${user.id}`),
  ([user]) => user.id  // Use only id as cache key
);

await fetchUser({ id: 1, name: 'Alice' });
await fetchUser({ id: 1, name: 'Bob' });  // Cache hit! Same id

function memoizeOne(fn) {
  let lastArgs = null;
  let lastResult;

  return function(...args) {
    // Check if args are the same as last call
    if (
      lastArgs !== null &&
      args.length === lastArgs.length &&
      args.every((arg, i) => arg === lastArgs[i])
    ) {
      return lastResult;
    }

    lastArgs = args;
    lastResult = fn.apply(this, args);
    return lastResult;
  };
}

// Perfect for React - only caches last result
const filterUsers = memoizeOne((users, query) => {
  console.log('Filtering...');
  return users.filter(u => u.name.includes(query));
});

filterUsers(users, 'A');  // "Filtering..."
filterUsers(users, 'A');  // cached (same args)
filterUsers(users, 'B');  // "Filtering..." (new args)
filterUsers(users, 'A');  // "Filtering..." (args changed)

function memoize(fn, maxSize = 100) {
  const cache = new Map();

  return function(...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      // Move to end (most recently used)
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value);
      return value;
    }

    const result = fn.apply(this, args);

    if (cache.size >= maxSize) {
      // Remove oldest (first) entry
      const firstKey = cache.keys().next().value;
      cache.delete(firstKey);
    }

    cache.set(key, result);
    return result;
  };
}

// Cache stays bounded at 100 entries
const memoizedFetch = memoize(fetchData, 100);

function UserList({ users, filter }) {
  // Memoize expensive computation
  const filteredUsers = useMemo(() => {
    return users.filter(u => u.name.includes(filter));
  }, [users, filter]);  // Only recompute if deps change

  // Memoize callback to prevent child re-renders
  const handleClick = useCallback((userId) => {
    console.log('Clicked', userId);
  }, []);  // Empty deps = same function reference

  return (
    <div>
      {filteredUsers.map(user => (
        <UserRow
          key={user.id}
          user={user}
          onClick={handleClick}  // Stable reference
        />
      ))}
    </div>
  );
}

// Memoize component to skip re-renders
const UserRow = React.memo(({ user, onClick }) => (
  <div onClick={() => onClick(user.id)}>{user.name}</div>
));

// Without memoization: O(2^n) - exponential!
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// With memoization: O(n) - linear!
function memoizedFib() {
  const cache = {};

  function fib(n) {
    if (n in cache) return cache[n];
    if (n <= 1) return n;
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
  }

  return fib;
}

const fib = memoizedFib();
fib(50);  // Instant! Without memo: years

// Or using our generic memoize
const fib = memoize((n) => {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

Common Mistakes

• Memoizing impure functions (functions with side effects)
• Using memoize for functions that rarely repeat inputs
• Not considering memory usage for large caches
• Using JSON.stringify for objects with circular references
• Forgetting that React.memo does shallow comparison

Interview Tips

• Implement memoize() with configurable cache key function
• Implement memoizeOne() for React-style single-result caching
• Explain when memoization helps vs hurts performance
• Know how useMemo and useCallback work in React
• Discuss cache invalidation strategies

Practice Problems

Apply this concept by solving these 2 problems

Related Concepts