LESSON 299 OF 415 · MEMOIZATION

Minimum Path Sum in Swift: O(n * m) Recursion with a 2D Cache

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

Add memoization to the previous recursive solution, so every cell is computed only once. Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 8

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 starts at the top-left cell, ends at the bottom-right cell, and may only move one cell down or one cell right at each step. The method returns the smallest possible sum of the numbers along such a path, including both end cells.

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). The target is O(n * m) time and O(n * m) extra space, where the grid has n rows and m columns.

Approach: the cheapest way from a cell to the corner, remembered

Define minSum(i, j) as the minimum sum of a path from cell (i, j) to the bottom-right corner. From a cell, the next move is either down to (i + 1, j) or right to (i, j + 1), so:

At the bottom-right cell, the path is that single cell: the answer is grid[i][j].
Everywhere else, the answer is grid[i][j] plus the smaller of minSum(i + 1, j) and minSum(i, j + 1).

The answer to the whole problem is minSum(0, 0). Written without a cache, the recursion reaches a cell once for every path that passes through it, and that number grows exponentially with the grid's size. Storing each cell's answer the first time makes every later visit a single array read. There are n * m cells and each is computed once with constant work, so the time is O(n * m), and the cache needs n * m entries.

Moves that leave the grid need a value too. The helper returns Int.max for those, so that the min never prefers them. On the last row only "right" stays inside the grid, and on the last column only "down" does.

Step by step

Declare the cache as a property at the top of the class: var cache: [[Int]] = []. The helper and minPathSum both reach it, so it doesn't need to be passed as an argument.
Size it in minPathSum by assigning cache a nested Array(repeating:count:): grid.count rows of grid[0].count zeros. A zero means "not computed yet".
Return minSum(grid, 0, 0). Every path starts in the top-left cell. You can write this line before the helper exists.
Declare the helper minSum(_ grid: [[Int]], _ i: Int, _ j: Int) -> Int.
Handle leaving the grid: if i >= grid.count or j >= grid[0].count, return Int.max.
Handle the target: if i and j are both on the last row and last column, return grid[i][j]. This is the base case.
Use the cache: if cache[i][j] > 0, return it. A cell still holding 0 has not been filled in.
Compute and store: best is grid[i][j] plus min(minSum(grid, i + 1, j), minSum(grid, i, j + 1)). Save it in cache[i][j].
Return best.

The solution in Swift

class Solution {
    var cache: [[Int]] = []

    func minSum(_ grid: [[Int]], _ i: Int, _ j: Int) -> Int {
        if i >= grid.count || j >= grid[0].count {
            return Int.max
        }
        if i == grid.count - 1 && j == grid[0].count - 1 {
            return grid[i][j]
        }
        if cache[i][j] > 0 {
            return cache[i][j]
        }
        let best = grid[i][j] + min(minSum(grid, i + 1, j), minSum(grid, i, j + 1))
        cache[i][j] = best
        return best
    }

    func minPathSum(_ grid: [[Int]]) -> Int {
        cache = Array(repeating: Array(repeating: 0, count: grid[0].count), count: grid.count)
        return minSum(grid, 0, 0)
    }
}

Swift details worth a closer look:

Nested Array(repeating:count:). The inner call builds one row of zeros, and the outer call makes grid.count copies of it. Arrays are values, so each row is independent: writing to cache[1][2] doesn't touch the other rows, unlike a shared reference in many other languages.
A property needs no inout. The helper changes cache directly, because it is a member of the same class instance. The recursion is also why cache is reset in minPathSum: a new call on the same object must not see an old grid's numbers.
Int.max as infinity. It is the largest 64-bit Int. Adding to it would overflow, and in Swift overflow stops the program. That never happens here, because the only way to add grid[i][j] to a result is after taking the min of two values, and at least one of them is a real sum: both moves leave the grid only at the bottom-right cell, which returns before the recursion.
grid[0].count is the number of columns. It is evaluated on every call, which is cheap, but it traps on an empty grid, where grid[0] doesn't exist.
Short-circuit conditions. In i >= grid.count || j >= grid[0].count, the right side runs only if the left is false, so grid[0] is never read after a failed row check. Row 0 always exists once the grid is non-empty.

Complexity

Time: O(n * m). Each cell does its real work once: two recursive calls and one addition. Each call is either a cache hit, a move off the grid, or that one-time computation. Every cell is the target of at most two calls (from above and from the left), so the total number of calls is at most about 2 * n * m. For the 3x3 example, the helper is called 17 times.

Space: O(n * m). The cache has one entry per cell. The recursion goes at most n + m calls deep, because every call moves down or right, which is small by comparison.

Edge cases and common mistakes

A single row or column. [[1, 2, 3]] returns 6 and [[1], [2], [3]] returns 6. Only one move ever stays inside the grid, and the other returns Int.max.
A single cell. [[5]] returns 5, straight from the base case.
Zeros in the grid. The "greater than 0" test treats a stored 0 as "not computed". A cell can have a true answer of 0 only if every number on its best path is 0. Then the answer is recomputed each time. The result is still right, but the speed-up is lost for those cells: on a 12x12 grid of zeros the helper runs about four million times, against 287 calls for a grid of ones. A separate marker, such as an array of optional values (Int? with nil for "not computed"), keeps the cache effective for every input.
Checking the base case after the bounds. The order in the code matters. The bounds check comes first so that no index out of range is ever used on grid or cache.
Not storing the result. Without cache[i][j] = best, the answer is still correct and takes exponential time.
Adding Int.max to something. Any code path that adds to Int.max crashes. Here the base case prevents it.
Empty grid. grid[0] traps. The lesson's tests use grids with 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