Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
14

DSA · Lesson 14 of 20 · 4 min

Dynamic Programming I: Memoization

This is how you turn an exponential-time recursive solution into a linear one, and explain the trade-off in an interview.

Dynamic Programming (DP) is an optimization technique. Memoization is the top-down, recursive way to do it. You use it when you find a recursive solution that's correct but too slow because it solves the same subproblem over and over.

You trade space for time. By storing the results of subproblems in a cache, you avoid re-computing them, drastically speeding up your code.

The Pattern: Overlapping Subproblems

The signal for memoization is a recursive function that repeatedly calls itself with the same arguments. Consider the Fibonacci sequence: fib(n) = fib(n-1) + fib(n-2).

To calculate fib(5), you need fib(4) and fib(3). To calculate fib(4), you need fib(3) and fib(2).

You can see fib(3) is needed twice. As n grows, the number of these "overlapping subproblems" explodes, leading to an exponential number of calls. This is the problem memoization solves.

Step 1: Write the Brute-Force Solution

In an interview, always start with the simple, brute-force recursive solution. It shows you understand the problem's structure before you optimize it. It also serves as the scaffold for your memoized solution.

Here is the naive, exponential-time Fibonacci function.

function fib(n: number): number {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

This works, but its time complexity is O(2^n). For n=40, this is over a billion operations. Unacceptable. This is your moment to identify the inefficiency and propose the fix.

Step 2: Add a Cache to Memoize Results

The fix is to add a cache (a plain object or a Map) to store results as they are computed. The logic is always the same three steps, inserted at the top of your recursive function.

  1. Check if the result for the current arguments exists in the cache. If yes, return it immediately.
  2. If not, compute the result as before.
  3. Before returning the result, store it in the cache.
function fibMemo(n: number, memo: { [key: number]: number } = {}): number {
    // 1. Check the cache
    if (n in memo) {
        return memo[n];
    }

    if (n <= 1) {
        return n;
    }

    // 2. Compute if not in cache
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);

    // 3. Store the result before returning
    memo[n] = result;
    return result;
}

By adding the memo object, we ensure that fibMemo for any given n is only ever computed once. The time complexity drops to O(n).

The trap: Forgetting to pass the memo object in the recursive calls. If you call fibMemo(n - 1) instead of fibMemo(n - 1, memo), each sub-problem gets a new, empty cache, and your optimization does nothing.

The space complexity is now O(n) to hold the cache and O(n) for the recursion call stack, for a total of O(n). This is the trade-off you must articulate.

Handling Functions with Multiple Arguments

When your function takes multiple arguments, you need a strategy for creating a unique cache key. A common method is to create a string by joining the arguments with a delimiter.

Consider the Grid Traveler problem: how many ways can you travel from the top-left to the bottom-right of an m x n grid, moving only right or down?

The state is defined by two numbers, m and n. A simple key is m + ',' + n.

function gridTraveler(m: number, n: number, memo: { [key: string]: number } = {}): number {
    const key = `${m},${n}`;

    if (key in memo) {
        return memo[key];
    }
    if (m === 1 && n === 1) return 1;
    if (m === 0 || n === 0) return 0;

    const result = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo);
    
    memo[key] = result;
    return result;
}

A subtle improvement: In this specific problem, gridTraveler(m, n) is the same as gridTraveler(n, m). You can optimize the cache by creating a canonical key, like Math.min(m, n) + ',' + Math.max(m, n). This demonstrates attention to detail.

The Memoization Playbook for Interviews

When you spot a problem with overlapping subproblems, follow these steps to present a clean, well-reasoned solution.

  1. State the brute-force approach. Acknowledge the recursive nature of the problem.
  2. Code the brute-force solution. Get a working, albeit slow, solution on the board.
  3. Analyze its complexity. Point out the exponential time complexity and explain that it's due to re-computing the same subproblems. Use a small example like fib(4) to illustrate the repeated work.
  4. Introduce memoization. Describe the "cache-and-return" strategy and the time-space trade-off.
  5. Modify the code. Add the memo object, the cache check, and the cache store.
  6. Analyze the improved complexity. Explain that the time is now proportional to the number of unique subproblems (O(n) for Fibonacci, O(m*n) for Grid Traveler) and the space is also proportional to that number.

This flow shows a methodical problem-solving process, which is exactly what interviewers are looking for.

Try it

Take the classic Climbing Stairs problem: you can climb 1 or 2 steps at a time. How many distinct ways can you climb to the top of n stairs? First, write the brute-force recursive solution. Then, add memoization to make it efficient. The state you need to cache is simply n.

Next: We'll move on to a data structure for efficiently managing ordered elements: Heaps and Priority Queues.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Graphs: Representation & Traversals

Next

Heaps and Priority Queues