Start learning free

LESSON 290 OF 415 · BACKTRACKING

Minimum Path Sum in Swift: Recursive Down-or-Right Search

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

This plain recursive solution recomputes the same cells many times, so it runs in exponential time, O(2n + m), and uses O(n + m) extra space for the recursion stack.

STEP 1 OF 5
    Ctrl + Enter to check

    SWIFT · BACKTRACKING

    Minimum Path Sum in Swift, explained

    Problem overview

    The method minPathSum receives a grid of non-negative integers, [[Int]]. You start in the top-left cell and finish in the bottom-right cell, and every move goes one cell down or one cell right. The sum of the numbers on the cells you pass through, including both ends, is the cost of the path. The method returns the smallest possible cost.

    For the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the cheapest path is 1, 3, 1, 1, 1 (right, right, down, down), with a cost of 7. The path through the 5 in the middle costs more.

    Approach: the cheapest path from a cell

    Think about the cost from an arbitrary cell (i, j) to the bottom-right corner, and call it minSum(grid, i, j). A path from that cell must pay for the cell itself and then continue either down, to (i + 1, j), or right, to (i, j + 1). It picks whichever continuation is cheaper, so:

    minSum(i, j) = grid[i][j] + min(minSum(i + 1, j), minSum(i, j + 1))

    Two cases end the recursion. If the cell is the bottom-right one, the path is that cell alone and costs grid[i][j]. If a move leaves the grid, it isn't a valid continuation. The lesson returns a huge value, Int.max, for such a move, so the min never picks it.

    On the bottom row only the right move is valid, and on the last column only the down move. The invalid move gives Int.max, and min takes the other one, so these cells need no special code.

    Step by step

    1. Declare the helper minSum above minPathSum. It takes the grid and the indices i and j without labels and returns an Int.
    2. Handle leaving the grid. If i >= grid.count (past the last row) or j >= grid[0].count (past the last column), return Int.max.
    3. Handle the target. If i is the last row index and j the last column index, return grid[i][j].
    4. Combine. Otherwise return grid[i][j] plus the smaller of the down result, minSum(grid, i + 1, j), and the right result, minSum(grid, i, j + 1).
    5. Start at the corner: minPathSum returns minSum(grid, 0, 0).

    The solution in Swift

    class Solution {
    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]
        }
        return grid[i][j] + min(minSum(grid, i + 1, j), minSum(grid, i, j + 1))
    }
    func minPathSum(_ grid: [[Int]]) -> Int {
        return minSum(grid, 0, 0)
    }
}

    The Swift details worth a closer look:

    • Why Int.max is safe to add to. In Swift, adding to Int.max doesn't wrap: it stops the program with an overflow error, even in optimized builds. The lesson avoids it because Int.max only ever appears as one side of a min, and the other side is always a real cost. Both neighbours of a cell can't be outside the grid at the same time, except for the bottom-right cell, which returns before reaching the sum. Adding grid[i][j] to the real cost is safe. If you rewrote the code to add first and compare after, you would hit the overflow.
    • Short-circuit checks. In i >= grid.count || j >= grid[0].count, the second test is evaluated only when the first is false. For an empty grid, the first test is already true at i = 0, so grid[0] is never read.
    • Nested arrays. [[Int]] is an array of arrays, and grid[i][j] reads row i, then column j. Passing it down the recursion doesn't copy it, because nothing modifies it.
    • The standard min. min(a, b) is a global function that returns the smaller of two comparable values.
    • Reading an out-of-range index crashes. A Swift array doesn't return a default for a bad index. The bounds checks before every read are what keep the recursion from stopping the program.

    Complexity

    Time: exponential. Every cell inside the grid makes two further calls, and different paths reach the same cell many times, each time repeating its whole subproblem. In a 3 by 3 grid the function is called 27 times, in 5 by 5 it is called 363 times, in 10 by 10 it is called 272,271 times and in 12 by 12 almost four million times. Remembering each cell's result the first time it is computed would make the time O(m * n) for an m by n grid, and later lessons on this problem do that.

    Space: O(m + n). The recursion advances one row or column per call, so the stack is never deeper than m + n - 1 frames. The grid is not copied.

    Edge cases and common mistakes

    • One cell. [[5]] starts on the target and returns 5.
    • A single row or column. [[1, 2, 3]] and [[1], [2], [3]] each return 6. There is only one path, and the out-of-grid moves are ignored through Int.max.
    • Choosing greedily. Always stepping to the smaller neighbour can lead into large numbers a few cells later. The recursion compares the full cost of both moves instead.
    • Forgetting the target's own value. The base case returns grid[i][j], not 0. The path includes both end cells.
    • Checking the target before the bounds. The order matters: reading grid[i][j] before checking that i and j are inside the grid would crash.
    • Empty grid. [] has no cells, and the method returns Int.max, which isn't a meaningful cost. The lesson assumes a grid with at least one cell.
    • Large grids. The call count grows so fast that grids beyond about 12 by 12 take a long time with this version.

    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.
    • [[1, 2], [1, 1]] gives 3.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free