LESSON 265 OF 348 · BACKTRACKING

Minimum Path Sum in Kotlin: 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

KOTLIN · BACKTRACKING

Minimum Path Sum in Kotlin, explained

Problem overview

You get a grid of non-negative integers as an Array<IntArray>. Starting at the top-left cell and moving only down or right, find a path to the bottom-right cell with the smallest sum of the numbers along the way, and return that 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).

Approach

Let minSum(grid, i, j) be the smallest sum of a path from cell (i, j) to the bottom-right cell. Every path begins with the cell's own value, and then it takes one of two moves, 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))

The recursion needs two stopping rules. At the bottom-right cell the path is that single cell, so the answer is its value. A move that leaves the grid is not a valid path at all, and we want it to lose every comparison, so it returns the largest possible Int.

The lesson states O(n * m) time and space. That bound belongs to the solutions that remember answers they have already computed. This first solution is the plain recursion, and it recomputes the same cells many times.

Step by step

Declare minSum above minPathSum. It takes the grid and the cell coordinates i (row) and j (column), and returns an Int.
Out of the grid. If i >= grid.size or j >= grid[0].size, the move left the grid. Return Int.MAX_VALUE, so the minimum never picks this branch.
Bottom-right cell. If i is the last row and j is the last column, return grid[i][j]. This is the base case that ends the recursion.
Recursive case. Return grid[i][j] plus minOf the path that goes down and the path that goes right.
Start at the top-left. minPathSum returns minSum(grid, 0, 0).

The solution in Kotlin

class Solution {
    fun minSum(grid: Array<IntArray>, i: Int, j: Int): Int {
        if (i >= grid.size || j >= grid[0].size) {
            return Int.MAX_VALUE
        }
        if (i == grid.size - 1 && j == grid[0].size - 1) {
            return grid[i][j]
        }
        return grid[i][j] + minOf(minSum(grid, i + 1, j), minSum(grid, i, j + 1))
    }

    fun minPathSum(grid: Array<IntArray>): Int {
        return minSum(grid, 0, 0)
    }
}

Kotlin details:

Why Int.MAX_VALUE is safe here. Adding anything to it would overflow, since Int is 32 bits and wraps silently: Int.MAX_VALUE + 1 becomes the most negative Int. The code never does that addition. The only call that can reach outside the grid from a cell other than the bottom-right one is a call that moves down from the last row or right from the last column, and then the other move stays inside the grid. At the bottom-right cell the function returns before it reaches the addition.
Array<IntArray> is an array of rows, each row a primitive IntArray. grid.size is the number of rows and grid[0].size is the number of columns.
minOf(a, b) is a standard function that returns the smaller value.
Short-circuit || and &&. The first check evaluates grid[0].size only when needed, and it comes before any read of grid[i][j], so the code never indexes outside the grid.

Following the example

For the 3 by 3 grid above, minSum(grid, 0, 0) is 1 + min(minSum(1, 0), minSum(0, 1)). Working the recursion down, minSum(2, 2) is 1, minSum(1, 2) is 1 + 1 = 2, minSum(0, 2) is 1 + 2 = 3 and minSum(0, 1) is 3 + min(minSum(1, 1), 3). Since minSum(1, 1) is 5 + 2 = 7, the right move wins and minSum(0, 1) is 6. The other move gives minSum(1, 0) = 8, so the smaller value 6 wins and the total is 1 + 6 = 7.

Complexity

Every call except the one at the bottom-right cell makes two more calls, and different paths lead to the same cell, so the same subproblem is solved again and again. On a grid of 1s the number of calls is 27 for 3 by 3, 363 for 5 by 5, 18875 for 8 by 8, 272271 for 10 by 10 and 3997447 for 12 by 12. The time is exponential in the size of the grid, not O(n * m). The recursion depth is at most n + m, so the stack uses O(n + m) space.

The O(n * m) bound is reached by remembering the answer for each cell the first time it is computed. The next solutions in this chapter do that. The recursive formula stays the same.

Edge cases and common mistakes

A single cell. The first call is already the bottom-right cell, so the answer is its value.
One row or one column. There is only one path. A grid [[1, 2, 3]] gives 6, and a column with 1, 2 and 3 also gives 6.
Adding to the sentinel. Returning Int.MAX_VALUE is safe only because a value is never added to the result of an out-of-grid call. If you change the structure, for example by using it as the value of a cell, watch out for overflow.
Checking the bounds after reading. Read grid[i][j] only after the first if, otherwise a cell outside the grid throws ArrayIndexOutOfBoundsException.
Swapping row and column. i is the row and is compared with grid.size. j is the column and is compared with grid[0].size.
Greedy choices. Taking the smaller neighbour at each step does not always give the best path, so the recursion must try both moves.
An empty grid. It isn't a valid input here. With arrayOf() the function returns Int.MAX_VALUE, since row 0 is already outside the grid.

Testing

The example grid returns 7.
[[5]] returns 5.
[[1, 2, 3]] returns 6.
A 12 by 12 grid of 1s returns 23 (22 moves, 23 cells), after about four million calls.

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

Start learning free