Problem overview
The function minPathSum receives a grid of non-negative numbers as an Array<IntArray>. A path starts at the top-left cell, ends at the bottom-right cell, and may only move down or right. The sum of a path is the total of every cell it visits, including both ends. The function 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. This lesson uses memoized recursion. The statement asks for O(n * m) time and O(n * m) extra space for a grid with n rows and m columns.
Approach: the best path from a cell does not depend on how you arrived
Define minSum(i, j) as the smallest sum of a path from cell (i, j) to the bottom-right corner. From any cell there are 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 bottom-right cell is the base case: the path is that single cell, so the answer is its own value. The answer to the whole problem is minSum(0, 0).
Without a cache, the recursion splits in two at every cell, and different routes reach the same cell again and again. The number of calls grows with the number of paths, which is exponential in the grid size. But there are only n * m different cells, and the answer for a cell never changes. Store each answer the first time it is computed and the total work drops to one computation per cell.
Step by step
- Create the cache in
minPathSum: avalholdinggrid.sizerows, each anIntArrayofgrid[0].sizezeros. Build it with theArray(size) { ... }constructor, so the lambda runs once per row and gives each row its own array. - Call the helper. Return
minSum(grid, cache, 0, 0), because every path starts in the top-left cell. - Declare
minSumwith the grid, the cache and the indicesiandj, returning anInt. - Handle moves that leave the grid. If
iis past the last row orjis past the last column, returnInt.MAX_VALUE. This is so large that the minimum never picks it. - Handle the target. At the bottom-right cell, return
grid[i][j]. This base case stops the recursion. - Check the cache. If
cache[i][j]is greater than 0, the cell was already computed; return that value. A cell still holding 0 has not been filled in. - Compute and store. Set
cache[i][j]togrid[i][j]plus the smaller of the answer from below and the answer from the right. - Return
cache[i][j].
The solution in Kotlin
class Solution {
fun minSum(grid: Array<IntArray>, cache: 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]
}
if (cache[i][j] > 0) {
return cache[i][j]
}
cache[i][j] = grid[i][j] +
minOf(minSum(grid, cache, i + 1, j), minSum(grid, cache, i, j + 1))
return cache[i][j]
}
fun minPathSum(grid: Array<IntArray>): Int {
val cache = Array(grid.size) { IntArray(grid[0].size) }
return minSum(grid, cache, 0, 0)
}
}
The Kotlin details worth a closer look:
- The line break after
+. The statement continues on the next line because the first line ends with the operator+, so the compiler knows the expression is unfinished. Starting the second line with+instead would end the statement early:val x = 1followed by a line+ 2leavesxequal to 1. Array<IntArray>. A grid is an array whose elements areIntArrayrows. The callArray(n) { IntArray(m) }buildsnseparate rows ofmzeros. Because the lambda runs for each row, no two rows share storage.Int.MAX_VALUEas a sentinel. Adding anything to it would overflow and wrap around to a negative number. That never happens here: the only calls that return it come from cells in the last row or column, and each of those has one other move that returns a real number. The bottom-right cell returns before it makes any recursive call.minOf. It returns the smaller of two values. Both calls are evaluated before it picks, which is fine because each one is cached after its first computation.- The cache is a
val. The reference never changes, but the rows inside can be written to.
Complexity
Time: O(n * m). Each cell's recurrence is computed once. Every later request for it is answered from the cache, and each cell is requested at most twice, by the cell above and the cell to its left.
Space: O(n * m). The cache has one entry per cell. The recursion goes as deep as the longest route, n + m - 1 calls, which is smaller.
Edge cases and common mistakes
- A single cell.
[[5]]returns 5, because the start is also the target. - A single row or column. Only one route exists.
[[1, 2, 3]]returns 6, since the move down always lands outside the grid and returns the huge value. - Cells with value 0. The cache uses 0 to mean "not computed yet". A cell whose best sum really is 0 is therefore recomputed on every request. The result stays correct, but the speed-up is lost: on a 12 by 12 grid of ones the function makes 287 calls, while a 12 by 12 grid of zeros makes 3,997,447. A separate marker such as -1 or a boolean table avoids the problem.
- Computing without storing. Returning the sum without writing it to
cache[i][j]gives correct answers but exponential time. - Greedy choices. Always stepping to the cheaper neighbour is not enough. A small cell can lead to expensive ones, so both options have to be compared by their full path sums.
Testing
[[1, 3, 1], [1, 5, 1], [4, 2, 1]]gives7.[[5]]gives5.[[1, 2, 3]]gives6.[[0, 0, 0], [0, 0, 0]]gives0.