Start learning free

LESSON 289 OF 414 · BACKTRACKING

Minimum Path Sum in Scala: Recursion Over Down and Right

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

This plain recursive solution recomputes the same cells many times, so it runs in exponential time, O(2n + m), and uses O(n + m) extra space for the recursion stack.

STEP 1 OF 5
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Minimum Path Sum in Scala, explained

    Problem overview

    The method minPathSum receives a grid of non-negative integers, an Array[Array[Int]] with m rows and n columns. A path starts at the top-left cell and ends at the bottom-right cell, moving only down or right. The method returns the smallest possible sum of the numbers on such a path.

    For this grid the answer is 7:

    1 3 1
1 5 1
4 2 1

    The path 1, 3, 1, 1, 1 (right, right, down, down) adds up to 7, and no other path does better.

    Approach: the best path from a cell

    Think about one cell at a time. Let minSum(grid, i, j) be the smallest sum of a path from cell (i, j) to the bottom-right corner. From that cell there are only two moves, down to (i + 1, j) or right to (i, j + 1). Whichever you choose, the cell's own value is paid, and then the rest of the path is the same problem from the new cell. So:

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

    Two cases stop the recursion. At the bottom-right cell the path is that cell alone, so its value is the answer. A move that leaves the grid is not a valid path, and the lesson gives it the largest possible Int, so a min never prefers it.

    This version follows the formula literally. It is correct but recomputes the same cells many times, because many paths pass through a given cell. The following lessons on this problem remember the results, which gives the O(n * m) time.

    Step by step

    1. Declare the helper minSum(grid: Array[Array[Int]], i: Int, j: Int): Int above minPathSum. The cell is passed as parameters so the recursion can start from any cell.
    2. Handle moves off the grid. If i >= grid.length or j >= grid(0).length, return Int.MaxValue.
    3. Handle the destination. If i == grid.length - 1 and j == grid(0).length - 1, return grid(i)(j).
    4. Combine. The last expression is grid(i)(j) plus math.min of the path that goes down and the path that goes right.
    5. Start at the top-left. minPathSum is just minSum(grid, 0, 0).

    The solution in Scala

    class Solution {

    def minSum(grid: 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)
        }
        grid(i)(j) + math.min(minSum(grid, i + 1, j), minSum(grid, i, j + 1))
    }

    def minPathSum(grid: Array[Array[Int]]): Int = {
        minSum(grid, 0, 0)
    }
}

    Scala details:

    • grid(i)(j). grid(i) is a row and the second pair of parentheses reads a cell. grid(0).length is the number of columns.
    • Int.MaxValue is 2147483647, the largest Int. Int arithmetic wraps silently, so adding to it would produce a large negative number. The code avoids that: the only cell with both neighbours outside the grid is the bottom-right one, which returns before adding. Every other cell has at least one neighbour inside the grid, so the min picks a real sum.
    • The last expression is the result. The final line of minSum has no return. The two earlier returns are early exits.
    • Evaluation of the arguments. Both recursive calls always run: math.min receives two finished values, so there is no shortcut.

    Complexity

    Time: exponential. Each call makes two more calls, and nothing is stored. On a grid of 1s the number of calls to minSum is 27 for 3 by 3, 1,343 for 6 by 6, 272,271 for 10 by 10 and 59,431,999 for 14 by 14. Each extra row and column multiplies the work.

    Space: O(m + n). Each call moves down or right, so the recursion is at most m + n - 1 calls deep.

    Caching the answer for each cell leaves m * n distinct answers, each computed in constant time, which is the O(n * m) time the later lessons reach.

    Edge cases and common mistakes

    • Single cell. [[5]] returns 5, since the start is also the destination.
    • Single row or column. [[1, 2, 3]] returns 6 and [[1], [2], [3]] returns 6. On the last row only the right move stays inside the grid, and on the last column only the down move does.
    • Small square. [[1, 2], [1, 1]] returns 3.
    • Empty grid. Array() has no rows, so the first check i >= grid.length is true before grid(0) is touched, and the method returns Int.MaxValue. The lesson's input always has at least one cell.
    • Order of the checks. The bounds check comes first because (i, j) may lie outside the grid, where reading grid(i)(j) would throw an ArrayIndexOutOfBoundsException. Only after it passes is the destination test safe.
    • Using 0 for a move off the grid. A move outside the grid must look worse than any real path. Returning 0 would make leaving the grid look free and give a sum that is too small.
    • Greedy choice. Always stepping to the smaller neighbour can fail, because a small cell may lead to expensive cells later. The recursion compares the whole remaining path of both moves.

    Testing

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