LESSON 300 OF 415 · MEMOIZATION

Minimum Path Sum in Swift: Bottom-Up Dynamic Programming on the Grid

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

SWIFT · MEMOIZATION

Minimum Path Sum in Swift, explained

Problem overview

The method minPathSum(_ grid: [[Int]]) -> Int receives a rectangular grid of non-negative integers. A path begins at the top-left cell, ends at the bottom-right cell, and moves only down or right. The method returns the smallest sum of the numbers on any such path, counting both end cells.

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, and no other path adds up to less.

Approach: build the answer cell by cell from the top-left

The key observation is that a cell can only be entered from the cell above it or from the cell to its left. Let best(i, j) be the smallest path sum from the top-left corner to cell (i, j). Then:

best(0, 0) is just grid[0][0].
On the first row, the only way in is from the left, so best(0, j) = grid[0][j] + best(0, j - 1).
In the first column, the only way in is from above, so best(i, 0) = grid[i][0] + best(i - 1, 0).
Every other cell takes the cheaper of the two ways in: best(i, j) = grid[i][j] + min(best(i - 1, j), best(i, j - 1)).

The answer is best of the bottom-right cell. Filling the cells row by row, left to right, means both neighbours are always final before they are used, so no recursion is needed. Each cell is computed in constant time, so the whole algorithm runs in O(n * m) for a grid of n rows and m columns.

This lesson stores the values in the grid itself, overwriting each cell with its best value. For the example, the grid becomes [[1, 4, 5], [2, 7, 6], [6, 8, 7]], and the bottom-right cell holds 7.

Step by step

Make a mutable copy: var grid = grid. Function parameters are constants in Swift, so the method couldn't write into the original. Because arrays are values, the copy is independent of the caller's grid.
Name the dimensions: let n = grid.count, m = grid[0].count. They are the number of rows and the number of columns.
Fill the first row. A loop with j over 1..<m adds grid[0][j - 1] to grid[0][j]. Cell (0, 0) stays as it is, and starting at 1 guarantees the left neighbour exists.
Fill the first column. A loop with i over 1..<n adds grid[i - 1][0] to grid[i][0]. Each step builds on the already updated value above.
Fill the rest. Two nested loops, i over 1..<n and j over 1..<m, add min(grid[i - 1][j], grid[i][j - 1]) to grid[i][j].
Return grid[n - 1][m - 1], the bottom-right cell.

The solution in Swift

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        var grid = grid
        let n = grid.count, m = grid[0].count

        for j in 1..<m {
            grid[0][j] += grid[0][j - 1]
        }

        for i in 1..<n {
            grid[i][0] += grid[i - 1][0]
        }

        for i in 1..<n {
            for j in 1..<m {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
            }
        }

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

Swift details worth a closer look:

var grid = grid shadows the parameter. Inside the method, the name grid now refers to the new mutable variable. It is legal and common. Swift copies lazily, so the actual duplication happens at the first write, and the caller's array is never changed. After the call, the grid that was passed in still holds its original numbers.
Half-open ranges. 1..<m counts from 1 up to m - 1. When m is 1, the range 1..<1 is empty, so a one-column grid skips the loop. That works because Swift accepts a range whose two ends are equal. A range whose upper bound is smaller than the lower bound, such as 1..<0, crashes, which is what an empty row would trigger.
Compound assignment on nested arrays. grid[i][j] += ... reads the element, adds, and writes it back in place. It works because grid is a var and the element type is Int.
Two constants in one let. let n = grid.count, m = grid[0].count declares two separate constants, both inferred as Int.
Overflow. Int is 64 bits, and overflow would stop the program. Sums of reasonable grids are far below that.

Complexity

Time: O(n * m). The three loops together touch every cell once, doing constant work for each.

Space: O(n * m) as written. The method copies the grid, and the copy serves as the table. The extra space is therefore one value per cell. Modifying the caller's array directly would avoid the copy, but the Swift version can't do that for a plain parameter. A single row of m numbers is enough to hold the running values, which would give O(m) extra space.

Edge cases and common mistakes

A single cell. [[5]] returns 5: all three loops run over empty ranges.
A single row or column. [[1, 2, 3]] returns 6 and [[1], [2], [3]] returns 6, because the first row (or first column) fill-in does the whole job.
Forgetting the first row and column. The general formula reads grid[i - 1] and grid[i][j - 1], which don't exist on the border. These cells need their own rule.
Using 0..<m. Starting at 0 would read grid[0][-1], an index out of range that crashes.
Taking the wrong neighbour. Using the maximum, or adding both neighbours, answers a different question. For the minimum, take the smaller of the two.
Swapping n and m. The bottom-right cell is grid[n - 1][m - 1]: n is the row count and m the column count. Swapping them returns a wrong cell, or crashes on a non-square grid.
Empty grid. grid[0] traps, so the method needs at least one cell.

Testing

[[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7.
[[1, 2], [1, 1]] gives 3.
[[1, 2, 3]] gives 6.
[[1], [2], [3]] gives 6.
[[5]] gives 5.

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

Start learning free