LESSON 265 OF 348 · BACKTRACKING

Minimum Path Sum in TypeScript: Recursive Backtracking

Practice O(2ⁿ) 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:

Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 5

Guided

Ctrl + Enter to check

TYPESCRIPT · BACKTRACKING

Minimum Path Sum in TypeScript, explained

Problem overview

The method minPathSum receives a grid of non-negative numbers, grid, with m rows and n columns. A path starts in the top-left cell, ends in the bottom-right cell, and at each step moves one cell down or one cell right. The sum of a path is the total of the numbers in the cells it visits, both end cells included. The method returns the smallest possible sum.

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). Going through the 5 in the middle, or the 4 in the corner, costs more.

Approach: ask "what is the best path from here?"

Every path from a cell continues in one of two ways: down or right. So the cheapest path from cell (i, j) is the cell's own number plus the cheaper of the cheapest path from the cell below and the cheapest path from the cell on the right:

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

That formula is the whole algorithm. Two rules complete it:

At the bottom-right cell the path is that single cell, so the answer is grid[i][j]. This stops the recursion.
A move that leaves the grid is not a path. It returns a number so large that Math.min never chooses it. That also handles the last row, where only "right" is possible, and the last column, where only "down" is possible.

The method tries every route, which is why the lesson is in the backtracking chapter. Different routes pass through the same cells, and each time the cell's answer is computed again from scratch. That repetition is what later lessons on this problem remove, and the complexity section shows the cost.

Step by step

Declare the helper minSum with grid: number[][] and the indices i and j, returning a number. It answers the question for one cell.
Stop at the edge. If i >= grid.length or j >= grid[0].length, the move left the grid, so return Number.MAX_VALUE.
Stop at the goal. If i is the last row and j is the last column, return grid[i][j].
Recurse. Return grid[i][j] plus Math.min of the two continuations: this.minSum(grid, i + 1, j) for down and this.minSum(grid, i, j + 1) for right.
Start from the corner. minPathSum returns this.minSum(grid, 0, 0).

The solution in TypeScript

class Solution {

    minSum(grid: 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];
        }
        return grid[i][j] + Math.min(this.minSum(grid, i + 1, j), this.minSum(grid, i, j + 1));
    }

    minPathSum(grid: number[][]): number {
        return this.minSum(grid, 0, 0);
    }
}

Tracing the example from the top: minSum(0, 0) is 1 + min(minSum(1, 0), minSum(0, 1)). The cell below holds 1 and its best continuation costs 7, so it gives 8. The cell to the right holds 3 and its best continuation costs 3, so it gives 6. The smaller of 8 and 6 is 6, and adding the starting 1 gives 7.

TypeScript details worth knowing:

Number.MAX_VALUE as "infinity". It is the largest finite number, about 1.8e308. Adding a small cell value to it gives the same value back, because the small amount is lost to rounding, so the sum never becomes Infinity. Only an edge move returns it, and Math.min ignores it whenever a real path exists.
== works here, because both sides are numbers. In TypeScript, === is the usual habit, as it never converts types.
Row length. A two-dimensional array in TypeScript is an array of arrays, so grid.length is the number of rows and grid[0].length the number of columns.
The type annotations are erased when TypeScript compiles to JavaScript; they do not check the grid at run time.

Complexity

Let the grid have m rows and n columns.

Time: exponential. Each call that is inside the grid makes two more calls, and nothing stores earlier answers. The number of calls grows with the number of different paths, which is about C(m + n - 2, m - 1). A test run counted 27 calls for the 3x3 example, 18,875 for an 8x8 grid, about 4 million for 12x12, and about 59 million for 14x14, where it took a third of a second. Doubling the side makes the work explode, so grids of a few dozen cells per side are out of reach for this version.

Space: O(m + n). The only memory is the recursion stack, and each call moves one step down or right, so the depth is at most m + n - 1.

Edge cases and common mistakes

One cell. [[5]] is already at the goal, so the answer is 5.
A single row or column. [[1, 2, 3]] gives 6: the only path takes every cell, and each "down" move leaves the grid and loses to "right".
Returning 0 at the edge. A move that leaves the grid must be very expensive, not free. With 0 the recursion would prefer stepping off the grid and undercount.
Checking the goal after the edge check. The edge check goes first, so the goal check can safely read grid[i][j].
Greedy choice. Always stepping to the smaller neighbour can fail, because a cheap cell now can lead to expensive cells later. Comparing whole continuations avoids that.
An empty grid. [] has no cells, and this method returns Number.MAX_VALUE rather than a sum. The lesson's grids always have at least one cell.

Testing

[[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7.
[[5]] gives 5.
[[1, 2, 3]] gives 6.
[[1], [2], [3]] gives 6.
[[1, 2], [1, 1]] gives 3.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free