Memoization
In one line
Memoization stores the result of each recursive call by its arguments, so a subproblem that repeats is computed once and then looked up, often turning exponential time into polynomial time.
What it is
Memoization is caching for function calls. Before computing f(x), check a table (usually a dictionary) for x. If it is there, return the saved answer. If not, compute it, save it, then return it. It only works for pure functions: the same arguments must always give the same result.
Applied to recursion, it is top-down dynamic programming. Naive Fibonacci makes about 1.6^n calls because it recomputes the same values again and again; with memoization each fib(k) is computed once, so fib(n) needs only O(n) work. In Python, functools.lru_cache (or functools.cache) adds this to a function with one line.
Why interviewers ask
It is the most natural bridge from a correct but slow recursive solution to an accepted one. Interviewers often expect you to write the brute-force recursion, notice overlapping subproblems, add a memo, and then state the new complexity as number of states times work per state. It also shows you can choose the right state (the arguments that fully describe a subproblem).
How it works
- 1Write the plain recursive solution and make sure it is correct.
- 2Identify the state: the arguments that change between calls. Everything the result depends on must be in the state, and it must be hashable (tuples, not lists).
- 3Before computing, check the memo for the state and return the stored value if present.
- 4After computing, store the result under that state.
- 5Analyse: time = number of distinct states x work per state, space = memo size + recursion depth.
Worked example · Fewest coins for amount 6 with coins [1, 3, 4]
- best(6) tries best(5), best(3) and best(2), adding 1 coin to the smallest.
- best(5) recurses down the 1-coin path first: best(4), best(3), best(2), best(1), best(0). best(0) = 0, best(1) = 1, best(2) = 2.
- best(3) = 1 + min(best(2), best(0)) = 1 + 0 = 1 and is stored. best(4) = 1 + min(best(3), best(1), best(0)) = 1 and is stored.
- best(5) = 1 + min(best(4), best(2), best(1)) = 1 + 1 = 2.
- Back in best(6): best(5) = 2, then best(3) is already in the memo (1), and best(2) is in the memo (2). best(6) = 1 + 1 = 2, using 3 + 3.
- Each amount 0..6 was computed once, so the work is O(amount x number of coins) = 7 x 3, instead of exploring every coin sequence.
Picture it
Memoization is like writing answers on sticky notes while doing homework. The first time you work out 17 x 23 you do the long multiplication and stick the answer on the wall. Every later time you need it, you just read the note.
Reference code
from functools import lru_cache
def min_coins(coins, amount):
@lru_cache(maxsize=None)
def best(rest):
# fewest coins that sum to rest, or infinity if impossible
if rest == 0:
return 0
if rest < 0:
return float("inf")
return 1 + min(best(rest - c) for c in coins)
answer = best(amount)
return -1 if answer == float("inf") else answer
def fib(n, memo=None):
# the same idea with an explicit dictionary
if memo is None:
memo = {}
if n < 2:
return n
if n not in memo:
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print(min_coins((1, 3, 4), 6)) # 2 (3 + 3)
print(min_coins((2,), 3)) # -1
print(fib(80)) # 23416728348467685
min_coins uses lru_cache on an inner function so each amount is solved once and the cache is not shared between different coin sets. fib shows the manual version with a dictionary passed down the calls; fib(80) returns instantly, while the naive version would take far too long.
Key patterns
lru_cache on an inner function
When: Python solutions where the extra inputs are fixed
How: Define the recursive helper inside the main function and decorate it with @lru_cache(maxsize=None), so the cache resets on each new input.
Index-based state
When: String and array problems (word break, decode ways, LIS)
How: Use positions i, j as the state instead of slices, which are slower and use more memory.
Multi-dimensional state
When: Grids, knapsack, edit distance
How: State is a tuple like (i, j) or (i, remaining_capacity); the memo has at most rows x columns entries.
Memo vs tabulation
When: Deciding between top-down and bottom-up
How: Memo only computes reachable states and is easy to write; tabulation avoids recursion depth limits and can reduce space by keeping one row.
Real-world use
React useMemo and React.memo
React's useMemo caches an expensive computed value and only recomputes it when its listed dependencies change, and React.memo skips re-rendering a component whose props are unchanged.
Build caches
Bazel and Gradle key each build step by a hash of its inputs and reuse the stored output when the hash matches, so unchanged modules are never rebuilt. It is memoization of build steps.
Python's regular expression cache
Python's re module keeps a cache of compiled patterns keyed by the pattern and flags, so repeated calls like re.match with the same pattern skip recompilation.
GraphQL DataLoader
DataLoader caches loads by key within a single request, so if several resolvers ask for user 42, the database is queried once and the same result is reused.
In a project
A writing app checks whether a pasted hashtag such as #bestcoffeeinlondon can be split into dictionary words for readability. The naive recursive splitter hangs on long tags.
- Define can_split(i) = whether the text from position i to the end can be split into words.
- Recurse: for each word that matches at position i, check can_split(i + len(word)).
- Memoize can_split by i, since the same suffix is reached through many different splits.
- Also memoize the chosen split for each i to return the words, and cap tag length at 100 characters.
Impact: There are only n start positions, so the time drops from exponential to O(n^2) substring checks. Tags that used to freeze the editor split instantly, and the code stayed the same shape as the readable recursive version.
Trade-offs
Use it when
- A recursive solution recomputes the same subproblems
- The function is pure: the result depends only on its arguments
- Only some of the possible states are reachable, so computing them lazily saves work
Avoid it when
- Subproblems do not repeat, as in merge sort; the cache just adds memory
- Recursion depth would exceed the stack limit; use bottom-up tabulation
- The function has side effects or depends on mutable outside state
Cost: Time = distinct states x work per state, for example O(amount x coins) for coin change and O(n) for Fibonacci. Space = number of stored states plus recursion depth.
Common mistakes
- Leaving a changing parameter out of the memo key, so different subproblems share one wrong answer.
- Passing lists to an lru_cache function, which raises TypeError because lists are not hashable; use tuples or indices.
- Using a mutable default argument like memo={} that silently keeps results between separate test cases.
- Memoizing a function that depends on global state that changes.
- Forgetting that memoized recursion can still hit the recursion limit for large n.
Interview questions
Quick revision
- Memoization = cache results by arguments; top-down DP.
- Only for pure functions.
- State must include every changing input and be hashable.
- Time = number of states x work per state.
- Python: @lru_cache(maxsize=None) or @cache.
- Avoid mutable default memo={} across calls.
- Hitting recursion limits? Switch to tabulation.
Check yourself
1. What is the time complexity of Fibonacci with memoization?
2. Why does @lru_cache fail on def f(nums, i) when nums is a list?
3. Which function is a good candidate for memoization?
4. A memoized function has states (i, j) with i < 100 and j < 50, and each state does O(10) work. What is the time?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.