Start learning free

LESSON 275 OF 348 · MEMOIZATION

Minimum Path Sum in TypeScript: O(n * m) Bottom-Up Dynamic Programming

Practice O(n2) - DP 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.
STEP 1 OF 5
    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 a path, counting both end cells.

    For [[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).

    Approach: build the answers from the top-left corner

    Define the value of a cell as the minimum sum of a path from the top-left cell to it. Then:

    • the top-left cell's value is just its own number;
    • a cell in the first row can only be reached from its left neighbour, so its value is its number plus the value to its left;
    • a cell in the first column can only be reached from above, so its value is its number plus the value above it;
    • any other cell can be reached from above or from the left, so its value is its number plus the smaller of those two neighbours' values.

    That is the whole recurrence. Computing the cells row by row, left to right, means both neighbours are always final before the cell that needs them. There is no recursion and no cache lookup: a plain double loop fills in the values, and the last cell holds the answer.

    Brute force would try every path, and the number of paths grows exponentially with the grid size. The table shares the work between paths: each cell is computed once from two stored values, so the running time is proportional to the number of cells.

    This lesson stores the values in grid itself: grid[i][j] becomes the minimum sum of a path to that cell. The original numbers are no longer needed once a cell's value has been computed, so overwriting them saves a separate table.

    Here is the example after each stage:

    start          first row      first column   all cells
1 3 1          1 4 5          1 4 5          1 4 5
1 5 1          1 5 1          2 5 1          2 7 6
4 2 1          4 2 1          6 2 1          6 8 7

    The bottom-right value, 7, is the answer. For the middle cell, the options are 4 from above and 2 from the left; the smaller is 2, and 5 + 2 = 7.

    Step by step

    1. Read the sizes once. Declare n (rows) and m (columns) in one let declaration. This keeps the loop headers short.
    2. Fill the first row. Loop j from 1 up to but not including m, adding grid[0][j - 1] to grid[0][j]. Cell (0, 0) stays as it is, and starting at 1 guarantees the left neighbour exists.
    3. Fill the first column. Loop i from 1 up to but not including n, adding grid[i - 1][0] to grid[i][0]. Each step builds on the value just updated above it.
    4. Fill the rest. With two nested loops starting at 1, add the smaller of grid[i - 1][j] and grid[i][j - 1] to grid[i][j], using Math.min.
    5. Return grid[n - 1][m - 1], the minimum sum of a path to the bottom-right cell.

    The solution in TypeScript

    class Solution {
    minPathSum(grid: number[][]): number {
        let n = grid.length, m = grid[0].length;

        for (let j = 1; j < m; ++j) {
            grid[0][j] += grid[0][j - 1];
        }

        for (let i = 1; i < n; ++i) {
            grid[i][0] += grid[i - 1][0];
        }

        for (let i = 1; i < n; ++i) {
            for (let j = 1; j < m; ++j) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[n - 1][m - 1];
    }
}

    Details worth a closer look:

    • One declaration, two variables. let n = grid.length, m = grid[0].length; declares both. TypeScript infers number for each.
    • The input is modified. Arrays are passed by reference, so the caller's grid is overwritten. After the call on the example, it reads [[1, 4, 5], [2, 7, 6], [6, 8, 7]]. If the caller still needs the original numbers, copy the grid first, for example with grid.map(row => [...row]).
    • += on an element. grid[i][j] += x reads the cell, adds x and writes the result back. The compiler checks that both sides are numbers, but nothing is checked at run time.
    • Loop order matters. The first-row and first-column loops come before the main loop because the main loop reads from them. The main loop reads grid[i - 1][j] and grid[i][j - 1], both already final.
    • Numbers are doubles. Sums stay exact as integers up to 2^53, far above any practical grid.

    Complexity

    Let the grid have n rows and m columns.

    Time: O(n * m). Each cell is updated once with constant work: the first row, the first column and the nested loops together touch every cell exactly once.

    Space: O(1) extra. The table lives in the input grid, and the method adds only a few variables. If you copy the grid to protect the original, the space becomes O(n * m). The memoized recursive version needs a cache of that size plus a recursion stack, so this one is lighter.

    Edge cases and common mistakes

    • A single cell. [[5]] skips all three loops and returns 5.
    • One row or one column. [[1, 2, 3]] returns 6 and [[1], [2], [3]] returns 6. Only one of the first two loops does work, and the nested loops don't run.
    • Empty input. The method assumes at least one row. For [], reading grid[0].length throws a TypeError, and for [[]] the method returns undefined.
    • Zeros. Cells holding 0 need no special treatment. Unlike a memoized version that uses 0 to mean "not computed", the table is filled in order, so no cell is ever tested for being empty.
    • Taking the greedy neighbour. Moving always to the smaller adjacent number can fail: in [[1, 2, 9], [3, 9, 9], [1, 1, 1]] it gives 22, while the best path sums to 7, and the table finds it.
    • Starting the loops at 0. The updates would read grid[-1][j] or grid[i][-1]. JavaScript arrays have no index -1, so grid[-1] is undefined and reading grid[-1][j] throws a TypeError; grid[i][-1] is undefined and turns the sum into NaN.
    • Mixing up n and m. Rows run to n and columns to m. With a non-square grid the loops would go out of range.

    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