Start learning free

LESSON 298 OF 414 · MEMOIZATION

Minimum Path Sum in Scala: O(n * m) with a Memoization Table

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:

Add memoization to the previous recursive solution, so every cell is computed only once. Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 8
    Ctrl + Enter to check

    SCALA · MEMOIZATION

    Minimum Path Sum in Scala, explained

    Problem overview

    The method minPathSum receives a grid of non-negative numbers, an Array[Array[Int]]. You start in the top-left cell, finish in the bottom-right cell, and may only move down or right. The method returns the smallest possible sum of the numbers on 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). The statement asks for O(n * m) time and O(n * m) extra space.

    Approach: a recursive minimum with a 2D cache

    Define minSum(grid, cache, i, j) as the smallest path sum from cell (i, j) to the bottom-right corner. A path from (i, j) starts by stepping down to (i + 1, j) or right to (i, j + 1), so

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

    Computed naively, this recomputes many cells, because different routes reach the same cell. The grid has only n * m cells, so a table of the same size remembers each answer once. After that, each cell costs constant work, and the whole computation is O(n * m).

    Two special cases anchor the recursion. A step that leaves the grid is not a valid path, so it must never be the minimum: it returns Int.MaxValue. The bottom-right cell is a path on its own, so it returns its own value.

    Step by step

    1. Create the cache with Array.ofDim[Int](grid.length, grid(0).length), a 2D array of the same size as the grid. Every entry starts as 0, meaning "not computed yet".
    2. Return minSum(grid, cache, 0, 0) as the last expression of minPathSum, since every path starts at the top-left cell.
    3. Declare minSum above minPathSum, with the grid and the cache as Array[Array[Int]], the indices i and j as Int, and an Int result.
    4. Out of the grid. If i >= grid.length or j >= grid(0).length, return Int.MaxValue, so the minimum never picks that move.
    5. The goal cell. If i and j are both on the last row and column, return grid(i)(j). This stops the recursion.
    6. Cache check. If cache(i)(j) > 0, the cell was computed before, so return it. A cell still holding 0 is not filled yet.
    7. Compute and store: cache(i)(j) becomes grid(i)(j) plus the smaller of the two recursive results, taken with math.min.
    8. Return cache(i)(j) as the last expression.

    The solution in Scala

    class Solution {
    def minSum(grid: Array[Array[Int]], cache: Array[Array[Int]], i: Int, j: Int): Int = {
        if (i >= grid.length || j >= grid(0).length) {
            return Int.MaxValue
        }
        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(minSum(grid, cache, i + 1, j), minSum(grid, cache, i, j + 1))
        cache(i)(j)
    }

    def minPathSum(grid: Array[Array[Int]]): Int = {
        val cache = Array.ofDim[Int](grid.length, grid(0).length)
        minSum(grid, cache, 0, 0)
    }
}

    The Scala details worth a closer look:

    • Arrays of arrays. An Array[Array[Int]] is indexed with two sets of parentheses: grid(i)(j). grid.length is the number of rows and grid(0).length the number of columns.
    • Array.ofDim[Int](rows, cols) allocates the rows and columns in one call. The elements start as 0, the default for Int. That default is what the "not computed" test relies on.
    • Updating an element. cache(i)(j) = value is the same as cache(i).update(j, value).
    • Int.MaxValue is safe here only because it is never added to. Adding 1 to it would wrap to Int.MinValue, since Int is 32 bits and overflow wraps silently. The only cell that has both moves off the grid is the bottom-right cell, and the goal check returns before the sum is built. Every other cell has at least one valid move, so the minimum is always a real sum.
    • The last expression is the result. The final cache(i)(j) needs no return, while the early exits use return.
    • math.min is the standard two-argument minimum for Int values.

    Complexity

    Time: O(n * m). There are n * m cells, and each is computed once. Every later call for the same cell returns from the cache, and each cell is requested by at most two neighbours, so the total number of calls is bounded by a small multiple of n * m.

    Space: O(n * m). The cache has one entry per cell. The recursion also goes up to n + m - 1 calls deep, which is smaller than the table.

    Edge cases and common mistakes

    • A single cell. [[5]] is both the start and the goal, so the answer is 5.
    • A single row or column. [[1, 2, 3]] gives 6, and [[1], [2], [3]] gives 6, because there is only one path.
    • The example. [[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7.
    • Zeros in the grid. The cache uses 0 to mean "not computed". A cell whose true answer is 0 (only possible when every cell on its best path is 0) is never recognised as cached, so it is recomputed every time it is reached. The result stays correct, but the speed does not: on a 14 by 14 grid of zeros the recursion makes about 59 million calls, against 391 for a grid of ones. A separate marker such as -1 would avoid this.
    • Returning 0 instead of Int.MaxValue off the grid. Out-of-grid moves would look like free paths, and the minimum would always choose them.
    • Forgetting the goal check. The bottom-right cell would take the minimum of two out-of-grid moves and return a huge value.
    • Forgetting to store in the cache. The result stays correct but takes exponential time.

    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.
    • [[0, 0], [0, 0]] gives 0.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free