LESSON 275 OF 348 · MEMOIZATION

Minimum Path Sum in Kotlin: O(n * m) Bottom-Up in Place

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

Guided

Ctrl + Enter to check

KOTLIN · MEMOIZATION

Minimum Path Sum in Kotlin, explained

Problem overview

The function minPathSum receives a grid of non-negative numbers as an Array<IntArray>. A path goes from the top-left cell to the bottom-right cell, moving only down or right, and its sum is the total of every cell it visits. The function returns the smallest path sum.

For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7, from the path 1, 3, 1, 1, 1. The earlier lessons solved this with recursion and a cache. This one is a plain loop version that needs no extra table.

Approach: build the answer from the start

Instead of asking "what is the best path from here to the end?", ask "what is the best path from the start to here?". Call that value best(i, j). A cell can only be entered from above or from the left, so

best(i, j) = grid[i][j] + min(best(i - 1, j), best(i, j - 1)).

The top-left cell is its own path. A cell on the first row has no cell above it, so it can only be reached from the left. A cell in the first column can only be reached from above. If the cells are visited row by row, left to right, then both neighbours of a cell are final by the time the cell is reached, and every value can be computed with one pass and no recursion.

The lesson saves memory by writing best(i, j) straight back into grid[i][j]. Each cell is read once after it has been finalised and is never needed in its original form again, so overwriting the input loses nothing the algorithm needs. For the example grid, the first row becomes [1, 4, 5], the first column becomes [1, 2, 6], and the interior cells follow in reading order: the centre becomes 7 (5 plus the smaller of 4 and 2), the cell to its right 6, the cell below it 8, and the bottom-right cell 7 (1 plus the smaller of 6 and 8).

Step by step

Read the sizes once. Store the number of rows in n and the number of columns in m, so the loop headers stay short.
Fill the first row. Loop j from 1 to m - 1 and add grid[0][j - 1] to grid[0][j]. Cell (0, 0) stays as it is. Each cell builds on the already updated cell to its left.
Fill the first column. Loop i from 1 to n - 1 and add grid[i - 1][0] to grid[i][0].
Fill the rest. With i from 1 and j from 1, add the smaller of grid[i - 1][j] and grid[i][j - 1] to grid[i][j]. The order guarantees both neighbours are already final.
Return grid[n - 1][m - 1], the best sum to the bottom-right cell.

The solution in Kotlin

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val n = grid.size
        val m = grid[0].size

        for (j in 1 until m) {
            grid[0][j] += grid[0][j - 1]
        }

        for (i in 1 until n) {
            grid[i][0] += grid[i - 1][0]
        }

        for (i in 1 until n) {
            for (j in 1 until m) {
                grid[i][j] += minOf(grid[i - 1][j], grid[i][j - 1])
            }
        }

        return grid[n - 1][m - 1]
    }
}

The Kotlin details worth a closer look:

until and empty ranges. 1 until m is 1, 2, up to m - 1. When m is 1 the range is empty and the loop body is skipped, so a single-column grid needs no special case.
Compound assignment on array elements. grid[0][j] += grid[0][j - 1] reads the element, adds, and writes it back. Kotlin allows this because grid[0] is an IntArray, whose elements can be assigned.
The array is modified. Parameters in Kotlin are read-only references, but the objects they point to are not. The function receives the caller's grid, not a copy, and overwrites it. Calling minPathSum a second time on the same grid gives a different answer: on the example grid, the first call returns 7 and the second returns 23, since the already summed values are summed again. Copy the grid first, or use a separate table, if the original is still needed.
minOf returns the smaller of two values.
val n and val m never change, so val is the right choice; Kotlin warns about a var that is never reassigned.
Overflow. Sums use Int, which is 32 bits, and wrap silently past about 2.1 billion. The sums here are small.

Complexity

Time: O(n * m). The first row costs m - 1 steps, the first column n - 1, and the nested loops (n - 1) * (m - 1). Together every cell is updated once.

Space: O(1) extra. The table lives in the input grid, and the only new variables are n, m and the loop counters. The statement allows O(n * m), so this is within budget. If you must keep the input intact, copying it brings the cost back to O(n * m).

Edge cases and common mistakes

A single cell. [[5]] skips all three loops and returns 5.
A single row or column. [[1, 2, 3]] returns 6 and [[1], [2], [3]] returns 6, from the first-row or first-column loop alone.
Starting the loops at 0. Starting j at 0 would read grid[0][-1] and throw an ArrayIndexOutOfBoundsException.
Skipping the border. If the interior loop also ran at i = 0 or j = 0, it would look at neighbours outside the grid. That is why the first row and column are handled separately.
Visiting in the wrong order. Looping from the bottom-right corner towards the start, for example, would read neighbours before they are final.
Returning the wrong cell. The answer sits in the bottom-right cell, grid[n - 1][m - 1]. The largest cell and the sum of the last row are not it.
Zeros. Cells of 0 cause no trouble here, since this version needs no "not computed" marker.

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, 0, 0]] gives 0.

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

Start learning free