Memoization Coding Problems: 21 Questions with Solutions
21 memoization coding problems — 2 easy · 5 medium · 14 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 21
- By difficulty: 2 easy · 5 medium · 14 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Memoisation (memoization in American spelling) stores a function's result for each set of arguments, so a recursion that would solve the same subproblem many times solves it once. It is the top-down form of dynamic programming: write the natural recursive definition, add a cache keyed by the arguments, and an exponential tree of calls collapses to one call per distinct state. The problems here practise spotting the repeated states, deciding what belongs in the key, and the cases where a cache is simpler than working out the order a table must be filled in.
How memoization works, step by step
fib(5); fib(n) = fib(n − 1) + fib(n − 2), fib(0) = 0, fib(1) = 1- Plain recursion for fib(5) recomputes the same smaller values again and again. Memoization keeps a table: before working anything out, a call checks the memo, and after working it out, it writes the answer there.
- Nothing is cached yet, so fib(5) calls fib(4), which calls fib(3), which calls fib(2), which calls fib(1): always the n − 1 branch first. fib(1) is a base case and returns 1 at once.
- fib(0) returns 0, so fib(2) = fib(1) + fib(0) = 1 + 0 = 1. Before returning, fib(2) writes its answer to memo[2], so no later call has to work it out again.
- fib(1) returns 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2, written to memo[3] on the way out. The base cases cost O(1) anyway, so only n ≥ 2 is cached.
- fib(4) needs fib(2) next. memo[2] = 1 is already there, so the call returns at once: the 2 calls a plain fib(2) would make below it never happen.
- fib(4) = fib(3) + fib(2) = 2 + 1 = 3, written to memo[4]. The memo now holds every value below fib(5).
- fib(5) needs fib(3) next. memo[3] = 2 is already there, so the call returns at once: the 4 calls a plain fib(3) would make below it never happen.
- fib(5) = fib(4) + fib(3) = 3 + 2 = 5, after 9 calls where plain recursion makes 15. Each fib(k) was computed once and every repeat was an O(1) lookup, so the time is O(n), with O(n) memory for the memo and the stack.
Memoization study plan
10 of the 21 Memoization problems (2 easy, 5 medium and 3 hard) over 7 days, about 6 h 20 min in all — the pattern first, then easiest to hardest. After that, the other 11 in the full list below are practice at your own pace. Then move on to Digit DP.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.
- Climbing Stairs Easy
- N-th Tribonacci Number Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Can I Win Medium
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Memoization: the essentials
When to reach for it
A recursion that is correct but slow because the same arguments keep coming back: a Fibonacci-like recurrence, the paths onward from each cell, Collatz step counts shared by many starting values. The arguments that change are the state; if the distinct states fit in memory, cache each answer. A cache also spares you the filling order a bottom-up table needs — that form is on Dynamic Programming.
The pattern
Write the recursion with its base cases, make sure everything the result depends on is an argument, then cache: Python's functools.cache does it in one line; elsewhere use a hash map keyed by the arguments, or an array holding a sentinel such as −1.
from functools import cache
def count_increasing_paths(grid): # strictly increasing paths, any length
m, n = len(grid), len(grid[0])
@cache
def paths_from(r, c): # the cell alone, plus every way onward
total = 1
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > grid[r][c]:
total += paths_from(nr, nc)
return total
return sum(paths_from(r, c) for r in range(m) for c in range(n))
Cost
Distinct states × work per state, plus a cache entry per state: O(m × n) above. The first call can recurse as deep as the longest chain of states, past Python's 1,000-frame default on large inputs.
Common mistakes
- Depending on state outside the arguments — a visited set, a running total — so a cached answer is reused where it no longer holds.
- A mutable argument as the key: Python refuses a list. Pass indices or tuples.
- A memo kept in a global or a class field and not cleared between test cases.
- Caching a recursion whose arguments rarely repeat, which spends memory for nothing.
Start with
- Climbing Stairs: the recursion that is exponential without a cache.
- Sort Integers by The Power Value: one cache shared by every starting value.
- Number of Increasing Paths in a Grid: a memo where a table's order would be awkward.
All memoization problems
Easy (2)
- N-th Tribonacci Number Math, Dynamic Programming
- Climbing Stairs Math, Dynamic Programming
Medium (5)
- Can I Win Math, Dynamic Programming, Bit Manipulation
- Maximum Number of Operations With the Same Score II Array, Dynamic Programming
- Different Ways to Add Parentheses Math, String, Recursion
- Longest Binary Subsequence Less Than or Equal to K String, Greedy, Dynamic Programming
- Sort Integers by The Power Value Dynamic Programming, Sorting
Hard (14)
- Count Visited Nodes in a Directed Graph Dynamic Programming, Graph
- Cat and Mouse Graph, Topological Sort, Math
- Length of Longest V-Shaped Diagonal Segment Array, Dynamic Programming, Matrix
- Maximum Strictly Increasing Cells in a Matrix Array, Hash Table, Binary Search
- The Earliest and Latest Rounds Where Players Compete Dynamic Programming
- Maximum Number of Groups Getting Fresh Donuts Array, Dynamic Programming, Bit Manipulation
- Zuma Game String, Dynamic Programming, Breadth-First Search
- Remove Boxes Array, Dynamic Programming
- Largest Color Value in a Directed Graph Graph, Topological Sort, Dynamic Programming
- Selling Pieces of Wood Array, Dynamic Programming
- Count All Possible Routes Array, Dynamic Programming
- Minimum Number of Days to Eat N Oranges Dynamic Programming
- Number of Distinct Roll Sequences Dynamic Programming
- Number of Increasing Paths in a Grid Array, Matrix, Dynamic Programming
Companies that ask memoization problems
- Google 20 problems on memoization
- Amazon 17 problems on memoization
- Adobe 2 problems on memoization
- Bloomberg 1 problem on memoization
- Flipkart 1 problem on memoization
- Hotstar 1 problem on memoization
- LinkedIn 1 problem on memoization
- Microsoft 1 problem on memoization
- Ola 1 problem on memoization
- Palantir 1 problem on memoization
Next topic: Digit DP