Start learning free

LESSON 299 OF 414 · MEMOIZATION

Minimum Path Sum in Scala: In-Place 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

    SCALA · MEMOIZATION

    Minimum Path Sum in Scala, explained

    Problem overview

    The method minPathSum receives a grid of non-negative numbers, an Array[Array[Int]] with n rows and m columns. 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 sum of the numbers along such a path.

    For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7: the path 1, 3, 1, 1, 1 goes right, right, down, down.

    Approach: turn each cell into the best sum that reaches it

    The earlier solutions of this problem work backwards from the goal with recursion. This one works forwards, with a loop, and it needs no extra table because it writes its results into the grid itself.

    After the algorithm runs, grid(i)(j) holds the minimum sum of a path from the top-left cell to (i, j). The reasoning splits cells into four kinds:

    • Cell (0, 0) is the start. Its best path is itself, so it keeps its value.
    • A cell in the first row can be reached only from its left neighbour, because there is no row above. Its best sum is its own value plus the left neighbour's best sum.
    • A cell in the first column can be reached only from above, so the same rule applies with the upper neighbour.
    • Any other cell can be reached from above or from the left. The best way to get there is through whichever neighbour has the smaller best sum, so the cell adds the smaller of the two.

    Going row by row, left to right, guarantees that both neighbours are final by the time a cell is processed. The answer is the value that ends up in the bottom-right cell.

    On the example, the first row becomes [1, 4, 5] and the first column [1, 2, 6]. Cell (1, 1) adds min(4, 2) = 2 to its 5 and becomes 7. Cell (1, 2) adds min(5, 7) = 5 to its 1 and becomes 6. Cell (2, 1) adds min(7, 6) = 6 to its 2 and becomes 8. Finally cell (2, 2) adds min(6, 8) = 6 to its 1 and becomes 7, which is the answer.

    Step by step

    1. Store the sizes. Declare n as grid.length (rows) and m as grid(0).length (columns) with val, because they are used in every loop header.
    2. Fill the first row. For j over 1 until m, add grid(0)(j - 1) to grid(0)(j). Starting at 1 guarantees the left neighbour exists, and it already holds its updated sum.
    3. Fill the first column. For i over 1 until n, add grid(i - 1)(0) to grid(i)(0).
    4. Fill the rest. For i over 1 until n and, inside it, j over 1 until m, 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) as the last expression of the method.

    The solution in Scala

    class Solution {
    def minPathSum(grid: Array[Array[Int]]): Int = {
        val n = grid.length
        val m = grid(0).length

        for (j <- 1 until m) {
            grid(0)(j) += grid(0)(j - 1)
        }

        for (i <- 1 until n) {
            grid(i)(0) += grid(i - 1)(0)
        }

        for (i <- 1 until n) {
            for (j <- 1 until m) {
                grid(i)(j) += math.min(grid(i - 1)(j), grid(i)(j - 1))
            }
        }

        grid(n - 1)(m - 1)
    }
}

    The Scala details worth a closer look:

    • Compound assignment on array elements. grid(0)(j) += x is shorthand for grid(0)(j) = grid(0)(j) + x. It works because Array is mutable, even though grid itself is a parameter and can't be reassigned.
    • The input is modified. Arrays are passed by reference, so the caller's grid is overwritten with the running sums. After the call on the example, it holds [[1, 4, 5], [2, 7, 6], [6, 8, 7]]. Copy the grid first, for example with grid.map(_.clone), if the original is still needed.
    • until excludes the end. 1 until m counts 1, 2, ..., m - 1. If m is 1, the range is empty and the loop body never runs.
    • Two indexes, two parentheses. A cell is grid(i)(j): first the row, then the column.
    • Overflow. Sums are stored in Int, which wraps silently beyond about 2.1 billion. For the lesson's grids this does not matter.

    Complexity

    Time: O(n * m). Each cell is updated exactly once, with a constant amount of work.

    Space: O(1) extra. The running sums overwrite the input, so no second table is allocated and there is no recursion. This is the difference from the memoized version, which needs a cache of n * m entries and a call stack.

    Edge cases and common mistakes

    • A single cell. For [[5]] all three loops are empty and the answer is 5.
    • A single row or column. [[1, 2, 3]] and [[1], [2], [3]] both give 6, from the first-row or first-column loop alone.
    • Skipping the border loops. Running only the nested loop from index 1 would leave the first row and column as plain values, so the paths along the edges would be missed.
    • Looping from 0. Starting the nested loop at 0 would read grid(-1)(j) and throw ArrayIndexOutOfBoundsException.
    • Using the original values. Adding a neighbour's original value instead of its updated sum gives a result that only looks one step back.
    • Reusing the grid. Calling the method twice on the same array keeps accumulating, and the second answer is wrong.

    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