Memoization Pattern

Why this pattern matters for LeetCode

Naive Fibonacci calls fib(n-1) and fib(n-2) for every n. fib(40) spawns over a billion calls. Memoization adds one line — store the result after computing it, return the stored result if you've already been here. The same call tree with memoization: each unique input is computed exactly once. O(n) calls instead of O(2^n). Memoization is the fastest path from a correct-but-slow recursive solution to a correct-and-fast one.

What the Memoization pattern is

Memoization is top-down dynamic programming: write a recursive function that solves the problem naturally, then add a cache (a Map or object) that stores the result for each unique input. Before doing any work, check if the input is in the cache. If yes, return the cached value. If no, compute it, store it, return it. The cache ensures each unique subproblem is solved at most once, turning exponential recursion into polynomial time.

Reach for Memoization when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Memoization

• ✓Fibonacci-style problems where f(n) depends on f(n-1) and f(n-2)
• ✓Climbing Stairs, Coin Change, House Robber — classic DP problems where recursion is intuitive
• ✓Grid path counting or minimum-cost paths where each cell's answer depends on its neighbors
• ✓Any recursive solution with a 'time limit exceeded' error on large inputs

When NOT to use Memoization

• ✕The recursive function has no overlapping subproblems — memoization adds overhead without benefit
• ✕The state space is too large to cache (billions of unique (arg1, arg2) pairs)
• ✕Bottom-up tabulation is clearer and uses less memory (no call stack overhead)
• ✕The problem is not a pure function of its arguments — side effects break caching

Better alternative: In those cases, bottom-up Dynamic Programming (tabulation) avoids recursion entirely and is often more space-efficient.

JavaScript code template

Climbing Stairs with memoization — O(n) time, O(n) space

function climbStairs(n, memo = new Map()) {
  if (n <= 1) return 1;              // base cases
  if (memo.has(n)) return memo.get(n); // cache hit

  const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
  memo.set(n, result);               // store before returning
  return result;
}

Three lines of change from naive recursion: add a `memo` parameter, check `memo.has(n)` before computing, and call `memo.set(n, result)` before returning. Every unique value of n is now computed exactly once. The first call to climbStairs(n) fills the cache top-down; every subsequent call to any previously-computed value is an O(1) lookup.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Write the recursive solution first without a cache — make sure it gives the correct answer on small inputs.
2. 2Add a Map (or plain object) as a parameter, defaulting to empty.
3. 3At the top of the function, before any computation, check if the current input is in the cache — if yes, return it.
4. 4Compute the result using the recursive calls (they will now benefit from the cache automatically).
5. 5Store the result in the cache before returning.
6. 6Verify the time complexity: each unique input is now computed once, so count the unique inputs, not the call tree.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Climbing Stairs

  f(n) = f(n-1) + f(n-2) — the canonical memoization example. Exponential without cache, O(n) with it.

  Premium→
• House Robber

  rob(i) = max(rob(i-2) + nums[i], rob(i-1)) — overlapping subproblems, perfect for a memo cache.

  Premium→
• Coin Change

  coins(amount) = 1 + min(coins(amount - coin) for each coin) — classic 1D memo DP.

  Premium→

Coming soon

• Unique Paths

  paths(r, c) = paths(r-1, c) + paths(r, c-1) — 2D memoization on a grid.

  Coming soon

Common mistakes beginners make

• ✕Checking the cache after the recursive calls — you must check before computing, otherwise the expensive work still happens.
• ✕Creating a new cache on every call — the cache must persist across all calls in the same problem. Pass it as a parameter or use a closure.
• ✕Caching a function with side effects — memoization assumes the same inputs always produce the same output. If the function modifies external state, the cache will return stale values.
• ✕Using an object as a cache with array or object keys — objects stringify their keys, so `{[1,2]: val}` becomes `{'1,2': val}`. Use a Map or stringify explicitly for multi-dimensional state.

Memoization (Top-Down) vs Tabulation (Bottom-Up)

Choose the right tool for the job.

Time and space complexity

Each unique set of arguments is computed exactly once and then cached. The time complexity equals the number of unique subproblems times the work per subproblem (excluding recursive calls). For Climbing Stairs, there are n unique values of n, each doing O(1) work — O(n) total. For 2D grid problems, there are n×m unique (row, col) pairs — O(n×m). Space is the cache size plus the call stack depth.

Frequently asked questions

What's the difference between memoization and dynamic programming?

Memoization IS dynamic programming — it's the top-down style. Classic DP (tabulation) is bottom-up: fill a table starting from the base cases and build up. Memoization is top-down: start from the original problem, recurse toward base cases, and cache on the way back. Same time complexity, different code shape.

When should I use memoization vs tabulation?

Use memoization when the recursive structure is obvious and you only need to compute subproblems that are actually reached. Use tabulation when all subproblems will be needed anyway, when you want to avoid call stack overhead, or when the recursion depth might cause a stack overflow.

How do I know which arguments to use as the cache key?

The cache key must uniquely identify the subproblem. Use all function arguments that change between recursive calls. If you call helper(i, remaining), the key is (i, remaining). If a function is a pure function of n, the key is just n. Arguments that never change (like the input array) don't need to be part of the key.

Why does memoization change O(2^n) to O(n)?

Without memoization, fib(n) spawns a binary call tree — each node branches into two calls. The tree has 2^n nodes. With memoization, once fib(k) is computed for any k, all future calls to fib(k) return immediately. Each of the n unique values is computed once. O(n) calls total, not O(2^n).