What Is Memoization? The Cache That Turns Exponential into Linear

You write a recursive solution, clean and correct, and it times out on every test case over n=40. Someone says "just memoize it" and suddenly it passes. Three lines of code. Your solution goes from getting killed by the judge to breezing through. But if you copy that pattern without understanding why it worked, you won't know when to reach for it yourself, and you'll miss it on the next problem that needs it.

Memoization is one specific optimization: store the result of a function call the first time you compute it, then return the stored result for every identical call after. That's the whole idea. The rest is details.

Your Recursive Fibonacci Is Doing Way Too Much Work

Start with the classic:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This looks harmless. It is lying to you. Call fib(6) and trace it. To compute fib(6), you need fib(5) and fib(4). To compute fib(5), you need fib(4) and fib(3). Notice: fib(4) gets computed twice. fib(3) three times. By the time you reach fib(2), it has been called eight times. It has no idea it's been here before.

The call tree doubles at every level, so the time complexity is O(2^n). For n=50, that's over a quadrillion function calls. Your laptop will not finish. Your laptop's grandchildren's laptops will not finish.

The root problem: the same subproblems get recomputed from scratch every time. Nothing is remembered. The function is doing enormous work that it has already done, obliviously, over and over again.

How Memoization Fixes This

Attach a cache (a dictionary) to the function. Before computing anything, check if you've already computed it. If yes, return immediately. If no, compute it, store it, return it.

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Now trace fib(6) again. You compute fib(4) once, store the result, and when fib(5) needs fib(4), it returns instantly. Every unique subproblem gets computed exactly once.

The time complexity drops from O(2^n) to O(n). Space is O(n) for the cache plus O(n) for the call stack. You traded exponential time for linear time at the cost of linear space. Almost always the right trade.

The naive fib(5) call tree has 25 nodes, with fib(3), fib(2), and fib(1) computed multiple times (shown in red). The memoized version computes each unique value exactly once in a straight chain.

Python Already Did This For You

Python's standard library has this built in:

from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

@cache (added in Python 3.9) wraps your function and handles the memo dictionary for you. @lru_cache(maxsize=None) does the same for older Python versions. Python looked at everyone writing memo = {} and initializing it at the top of every recursive function and felt collective embarrassment on our behalf.

In an interview, using the decorator is fine as long as you can explain what it does. If the interviewer asks "what does @cache do?" and your answer is a blank stare, you've made things worse.

In TypeScript, you do this manually:

function fib(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n)!;
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

What Makes a Problem Memoizable?

Not every recursive function benefits from memoization. Two conditions have to hold.

Overlapping subproblems: the same inputs appear in multiple recursive calls. If every call has unique inputs, there's nothing to cache. Fibonacci has this. Merge sort doesn't (each half is distinct data).

Referential transparency: the function returns the same output for the same input every time, with no side effects. If your function reads from a database or depends on external state, memoizing it silently returns stale results.

When both conditions hold, memoization can eliminate redundant computation and turn exponential recursion into polynomial time.

From O(2^n) to O(n): What Actually Changed

Here's a useful mental model. With memoization, the total work equals:

time = (number of unique states) × (work per state, excluding recursive calls)

For Fibonacci: there are n unique values, and each takes O(1) work once the subproblem results are cached. Total: O(n).

For a 2D grid problem like unique paths (counting ways to reach the bottom-right corner from top-left), the state is a (row, col) pair. There are m × n unique states, each taking O(1) work. Total: O(m × n). The naive recursion without memoization revisits each cell exponentially many times.

Space costs two things: the memo table (one entry per unique state) and the call stack (as deep as your recursion goes). For Fibonacci, both are O(n). For grid problems, the table is O(m × n) but the stack is O(m + n), the length of the longest path from top-left to bottom-right.

How Memoization Shows Up in Interviews

You'll recognize a memoization opportunity when:

You write a recursive solution and realize you're passing the same arguments in multiple branches
The problem asks for a count, minimum, maximum, or yes/no over all possible ways to do something
You see "number of ways," "minimum cost," "can you reach," or "longest subsequence"
Your naive solution times out and you feel that specific kind of shame

The standard move is to write the naive recursive solution first, briefly admire it, realize it's O(2^n), then identify the repeated work by noting which parameters uniquely determine the output. Those become your cache keys. Add a memo dictionary keyed on those parameters and suddenly you've transformed exponential into polynomial.

# Coin change: minimum coins to make amount
def coin_change(coins, amount):
    memo = {}

    def dp(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float('inf')
        if remaining in memo:
            return memo[remaining]
        memo[remaining] = 1 + min(dp(remaining - c) for c in coins)
        return memo[remaining]

    result = dp(amount)
    return result if result != float('inf') else -1

State: remaining amount. Unique states: amount + 1 values (0 through amount). Work per state: O(k) where k is the number of coins. Total time: O(amount × k). Without memoization, this would be O(k^amount).

The key discipline is identifying the minimum set of parameters that uniquely determines the return value. Those are your cache keys. Extra parameters bloat the cache and miss hits. Missing parameters give wrong answers.

Memoization vs Tabulation: When to Use Which

Memoization is top-down: you start from the answer you want and recurse toward base cases, caching as you go. Tabulation (bottom-up DP) fills a table starting from base cases and builds toward the answer.

Both give the same time complexity. Memoization is often easier to write because you follow the natural recursive structure of the problem. Tabulation avoids recursion overhead and stack overflow risk for very deep inputs, and sometimes allows space optimizations (keeping only the last few rows instead of the whole table).

In interviews, start with memoization if the recursive structure is clear. It's faster to write correctly under pressure, it maps directly onto the recursive thinking you'll narrate aloud, and you can mention tabulation as a follow-up optimization. When the interviewer asks "can we do better on space?", that's your cue.

See memoization vs tabulation for a deeper breakdown of the tradeoffs, and bottom-up dynamic programming if you want to see the table-filling approach applied to the same problems.

Say This When You Apply It

When you use memoization in an interview, don't just add a dictionary and stare at the interviewer. State three things explicitly:

"I notice dp(x) is called multiple times with the same argument, so I'll cache results."
"The cache key is x because that's the only thing that determines the return value."
"This changes the time complexity from O(exponential) to O(n), and adds O(n) space for the cache."

Most candidates add the dictionary silently, which leaves the interviewer genuinely unsure whether you understood what you did or just copied a pattern you once saw. Stating the complexity change explicitly is what separates a 3 from a 4 on the problem-solving dimension. The code is the same. The narration is what they're actually scoring.

Practice narrating this out loud before your interview. SpaceComplexity gives you voice-based mock interviews with rubric feedback on exactly this: how well you explain your reasoning as you code.

Where This Goes Wrong

Passing mutable default arguments as the memo. In Python, def fib(n, memo={}) shares the same dictionary across all function calls, across your entire program's lifetime. It works for Fibonacci because Fibonacci values don't change. It will cause mysterious bugs somewhere else because you'll call a different memoized function and get results from a previous invocation you didn't know it remembered. Prefer passing None and initializing inside the function, or just use @cache.

Forgetting to return the stored value. You compute memo[n] = ... and then hit a return that bypasses the cache read. Your function produces correct output. The cache never gets populated. You get O(2^n) performance with O(n) extra memory for a dictionary you aren't using.

Memoizing functions with side effects. If your function prints, writes to a list, or does anything besides return a value, caching silently skips those effects on repeated calls. The cache doesn't know about side effects. It only knows about return values. Your logging will vanish on cache hits. The bug report will say "it stops printing after the first call." You will spend an embarrassing amount of time on this.

Choosing the wrong cache key. If some parameter that affects the output isn't included in the key, the cache returns wrong answers with no error. The function returns. The tests pass on the happy path. The edge case fails in production, silently, with a wrong number.