Start learning free

LESSON 274 OF 348 · MEMOIZATION

Minimum Path Sum in TypeScript: O(n * m) with Memoization

Practice O(n2) - Memoization Read the full explanation

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 8
    Ctrl + Enter to check

    TYPESCRIPT · MEMOIZATION

    Minimum Path Sum in TypeScript, explained

    Problem overview

    The method minPathSum receives a grid of non-negative numbers, a number[][]. You start at the top-left cell and must reach the bottom-right cell, moving only down or right. The method returns the smallest possible sum of the numbers along such a path, including both end cells.

    For the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7, from the path 1, 3, 1, 1, 1: right, right, down, down. Every path has exactly the same number of cells, so only their values differ.

    Approach: recursion with a cache

    Think backwards from a cell. The cheapest path from cell (i, j) to the bottom-right corner starts with the cell's own value, then continues from either the cell below or the cell to the right. Take whichever of those two continuations is cheaper:

    minSum(i, j) = grid[i][j] + min(minSum(i + 1, j), minSum(i, j + 1))

    Without a cache this recursion explores every path. The number of paths in a grid grows exponentially, because the same cell is reached from many routes and its answer is recomputed each time. But the answer for a cell never depends on how you got there. So the first time you compute minSum(i, j), store it; every later request is a lookup. Each of the n * m cells is computed once, in constant time, so the total is O(n * m) time and O(n * m) space for the cache, as the statement asks.

    Step by step

    1. Build the cache as a const of type number[][]. Start with an empty array and, for each row of grid, push new Array(grid[0].length).fill(0). The cache then has the same dimensions as the grid and holds zeros. const only forbids reassigning the variable, so pushing rows is allowed.
    2. Call the helper before writing it: return this.minSum(grid, cache, 0, 0), because every path starts in the top-left cell.
    3. Declare minSum with grid and cache as number[][], i and j as number, returning a number. The same cache goes into every call, so all of them share it.
    4. Off-grid moves. If i is past the last row or j is past the last column, return Number.MAX_VALUE, a number so large that Math.min never chooses it.
    5. Base case. At the bottom-right cell the path is that cell alone, so return grid[i][j]. This stops the recursion.
    6. Cache check. If cache[i][j] is greater than 0, the cell was computed already, so return it. A cell still holding 0 has not been filled in.
    7. Compute and store. Set cache[i][j] to grid[i][j] plus the smaller of the answers for the cell below and the cell to the right.
    8. Return cache[i][j].

    The solution in TypeScript

    class Solution {
    minSum(grid: number[][], cache: number[][], i: number, j: number): number {
        if (i >= grid.length || j >= grid[0].length) {
            return Number.MAX_VALUE;
        }
        if (i === grid.length - 1 && j === grid[0].length - 1) {
            return grid[i][j];
        }
        if (cache[i][j] > 0) {
            return cache[i][j];
        }
        cache[i][j] = grid[i][j] +
            Math.min(this.minSum(grid, cache, i + 1, j), this.minSum(grid, cache, i, j + 1));
        return cache[i][j];
    }

    minPathSum(grid: number[][]): number {
        const cache: number[][] = [];
        for (let i = 0; i < grid.length; ++i) {
            cache.push(new Array(grid[0].length).fill(0));
        }
        return this.minSum(grid, cache, 0, 0);
    }
}

    Details worth a closer look:

    • A fresh row each time. new Array(grid[0].length).fill(0) creates a new array on every loop iteration. Writing new Array(rows).fill(new Array(cols).fill(0)) instead would fill the outer array with the same inner array repeated, so a write to one row would show up in all of them.
    • Number.MAX_VALUE as infinity. It is the largest finite double, about 1.8e308. Adding a small number to it gives the same value back, because the small number is lost to rounding, so even a sum that includes it stays huge and never wins the minimum. In this solution it is only ever an argument to Math.min, whose other argument is a real path sum. The value Infinity would behave the same way.
    • Why the cell below and the cell to the right are enough. In the last row, the move down is off-grid and returns the huge value, so the minimum picks the move right. In the last column it is the other way around.
    • Types. The annotations on the parameters and the cache are erased when the code is compiled to JavaScript. They help the compiler find mistakes, but they don't convert or check values at run time.
    • Recursion depth. A path has n + m - 1 cells, so the recursion goes about that deep. That is small for ordinary grids.

    Complexity

    Let the grid have n rows and m columns.

    Time: O(n * m). Each cell's formula runs once, and each cell is requested at most twice more by its neighbours above and to the left, which return from the cache. That is a constant number of calls per cell.

    Space: O(n * m). The cache has one entry per cell. The call stack adds another O(n + m), which doesn't change the bound.

    Edge cases and common mistakes

    • A single cell. [[5]] is at the bottom-right already, so the answer is 5.
    • One row or one column. [[1, 2, 3]] gives 6 and [[1], [2], [3]] gives 6: there is only one path, and the off-grid check removes the impossible move.
    • Zeros in the grid. The check cache[i][j] > 0 treats 0 as "not computed yet". If the true answer for a cell is 0, which happens when every cell from there to the corner is 0, the cell is recomputed on every visit and the speed advantage is lost. The result is still correct. In a test, a 14 by 14 grid of zeros took about 59 million calls, against 391 for a grid of ones of the same size. A separate marker, such as filling the cache with -1 and testing against it, avoids the problem. Grids with positive numbers, as in the examples, don't trigger it.
    • Empty grid. The method assumes at least one cell. For [[]] it returns Number.MAX_VALUE, the off-grid value, not 0.
    • Greedy choices. Always stepping to the smaller neighbour is not correct. In [[1, 2, 9], [3, 9, 9], [1, 1, 1]] the cheaper first step, right onto the 2, leads into a 9 with no way around it, and the greedy path sums to 22. The best path goes down the left side and along the bottom, and sums to 7. Only comparing the full remaining costs is safe.
    • Forgetting to store. If the formula's result isn't written into cache[i][j], the recursion is correct but explores every path.
    • Row and column bounds mixed up. Rows are checked against grid.length and columns against grid[0].length.

    Testing

    • [[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7.
    • [[1, 2, 3], [4, 5, 6]] gives 12.
    • [[5]] gives 5.
    • [[1, 2, 3]] gives 6.
    • [[1], [2], [3]] gives 6.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free