Skip to content
Hello Python
Pattern1 Practice1 Interview

Memoization

Cache top-down subproblem results so overlapping recursive states are solved only once. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Memoization when the prompt's constraints and required operations match this shape: Cache top-down subproblem results so overlapping recursive states are solved only once.

Pybit demonstrates the Memoization decision pattern in a professional coding interview workspace.
On this page · Cache by the Complete Recursive State

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Memoization Code Labs

Cache by the Complete Recursive State

Memoization stores the answer to a recursive subproblem under a key containing every input dimension that affects future results. Omitting position, budget, or mode can merge different states incorrectly.

Check the Cache Before Branching

After base cases as appropriate, return a cached result before generating children. This prevents the exponential recursion tree from recomputing an already solved state.

Trace Memoized Calls

Reference
def memo_fibonacci_trace(n):
    cache={0:0,1:1};events=[]
    def solve(value):
        if value in cache:events.append([value,True,cache[value]]);return cache[value]
        result=solve(value-1)+solve(value-2);cache[value]=result;events.append([value,False,result]);return result
    solve(n);return events
Practice

Implement memo_fibonacci_trace(n). Return [n,cache_hit,value] events in call order while computing Fibonacci.

Public tests

  • Reuse completed states

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Store Only Completed Results

Cache the final value after all dependencies return. Storing a partial result can corrupt overlapping calls; cyclic state graphs need a separate active marker rather than pretending partial work is complete.

Memoize Minimum Grid Path Cost

Reference
def minimum_path_cost(grid):
    cache={}
    def solve(row,col):
        if row==len(grid)-1 and col==len(grid[0])-1:return grid[row][col]
        if (row,col) in cache:return cache[(row,col)]
        best=float("inf")
        if row+1<len(grid):best=min(best,solve(row+1,col))
        if col+1<len(grid[0]):best=min(best,solve(row,col+1))
        cache[(row,col)]=grid[row][col]+best;return cache[(row,col)]
    return solve(0,0)
Practice

Implement minimum_path_cost(grid). Move only right or down from top-left to bottom-right and return minimum cell sum.

Public tests

  • Cache the complete row-column state

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Memoization or Bottom Up

Choose memoization when the recurrence is natural and only a subset of states is reachable. Choose bottom-up tabulation for predictable order, no recursion depth, and easier space compression. Both reduce work to distinct states times transitions.

Explain It in an Interview

Say: “This tuple is the complete state. Before branching I reuse a completed cached result; otherwise I solve dependencies and store once.” Count cache size, call-stack depth, and key-construction cost.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Memoization invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Memoization decision loopO(rows * cols)O(rows * cols)Define a recursive cell state and memoize the number of paths from each cell to the destination.

Space

O(rows * cols) for the focused Memoize Grid Paths implementation.

Assumptions

  • The base cases exactly classify invalid and terminal states. Every remaining path starts down or right, so summing those memoized subproblems counts every valid path once.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise Memoization invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Equal state keys always have equal remaining answers.
  3. The cache stores both successful and zero or impossible results.
  4. Define recursive state by the current cell. Preserve this property after every transition.
  5. Cache every subproblem result including zero-path states. Preserve this property after every transition.

When To Use Or Avoid Memoization

Use It When

  • Use Memoization when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when equal state keys always have equal remaining answers.

Choose Another Tool When

  • Avoid Memoization when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Memoize Grid Paths before optimizing.

Avoid

def count_grid_paths(rows, cols, blocked):
    pass

Use instead

from functools import lru_cache

def count_grid_paths(rows, cols, blocked):
    blocked_cells = {tuple(cell) for cell in blocked}
    @lru_cache(None)
    def visit(row, col):
        if row >= rows or col >= cols or (row, col) in blocked_cells:
            return 0
        if row == rows - 1 and col == cols - 1:
            return 1
        return visit(row + 1, col) + visit(row, col + 1)
    return visit(0, 0)

Where you will hit this: Memoize Grid Paths(opens in a new tab)

Breaking the maintained state

Treats a blocked destination as success by checking destination first.

Prevent it: Use the public tests and preserve this state: Equal state keys always have equal remaining answers.

Avoid

from functools import lru_cache
def count_grid_paths(rows,cols,blocked):
    blocked={tuple(x) for x in blocked}
    @lru_cache(None)
    def f(r,c):
        if r==rows-1 and c==cols-1:return 1
        if r>=rows or c>=cols or (r,c) in blocked:return 0
        return f(r+1,c)+f(r,c+1)
    return f(0,0)

Use instead

from functools import lru_cache

def count_grid_paths(rows, cols, blocked):
    blocked_cells = {tuple(cell) for cell in blocked}
    @lru_cache(None)
    def visit(row, col):
        if row >= rows or col >= cols or (row, col) in blocked_cells:
            return 0
        if row == rows - 1 and col == cols - 1:
            return 1
        return visit(row + 1, col) + visit(row, col + 1)
    return visit(0, 0)

Where you will hit this: Memoize Grid Paths(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(rows * cols).

Avoid

from functools import lru_cache
def count_grid_paths(rows,cols,blocked):
    blocked={tuple(x) for x in blocked}
    @lru_cache(None)
    def f(r,c):
        if r==rows-1 and c==cols-1:return 1
        if r>=rows or c>=cols or (r,c) in blocked:return 0
        return f(r+1,c)+f(r,c+1)
    return f(0,0)

Use instead

from functools import lru_cache

def count_grid_paths(rows, cols, blocked):
    blocked_cells = {tuple(cell) for cell in blocked}
    @lru_cache(None)
    def visit(row, col):
        if row >= rows or col >= cols or (row, col) in blocked_cells:
            return 0
        if row == rows - 1 and col == cols - 1:
            return 1
        return visit(row + 1, col) + visit(row, col + 1)
    return visit(0, 0)

Where you will hit this: Maximum Contiguous Subarray Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.