64. Minimum Path Sum

Problem Statement

You are given an m x n grid of non-negative integers. Starting at the top-left cell (0, 0), you must reach the bottom-right cell (m-1, n-1) by moving only right or down at each step. Your task is to return the minimum possible sum of the values along any valid path, including both the starting and ending cells.

Constraints:

• m $==$ grid.length
• n $==$ grid[i].length
• $1 \leq$ m, n $\leq 200$
• 0$ \leq$ grid[i][j] $\leq 200$

Examples

Why Recursive Approach is Impractical

A path’s sum depends only on the cells you step on, and every move reduces the remaining distance to the goal, so the problem naturally suggests comparing different routes.

A straightforward brute-force idea is: from each cell, recursively try moving right and down, compute the minimum sum to the end, and take the smaller result. This works, but it repeats the same subproblems many times.

This solution has an exponential, roughly $O(2^{m+n})$ time complexity because at most positions you branch into two choices (right/down), generating a huge number of paths. The space complexity of this solution is $O(m+n)$ for recursion depth (the longest path length), ignoring output.

Because this repeated work is the main bottleneck, we switch to a method that reuses results instead of recomputing them.

Optimal Solution using Dynamic Programming

We use the idea that to arrive at the cell (i, j), the previous step must be either from (i-1, j) (from above) or (i, j-1) (from left). If we already know the cheapest cost to reach those neighbors, the cheapest cost to reach (i, j) is just the current cell value plus the smaller of the two neighbor costs. This leads to the standard update: grid[i][j] += min(grid[i-1][j], grid[i][j-1]) once the borders are prepared.

Algorithmic Steps

This algorithm is implemented as follows:

1. Store the number of rows and columns of the grid in variables m and n respectively.
2. Iterate through the grid, row by row, using an outer loop over i.
   1. For each row, iterate through its columns using an inner loop over j.
      1. When you are at the starting cell (0, 0),
         1. Leave it unchanged and move to the next iteration.
      2. If the cell is in the first row (i == 0 and j > 0),
         1. It can only be reached from the left, so add the value of the left cell to it.
      3. If the cell is in the first column (j == 0 and i > 0),
         1. It can only be reached from above, so add the value of the above cell to it.
      4. For all other cells,
         1. Take the smaller of the accumulated sums from the top and left neighbors, add it to the current cell.
3. After filling the grid, return the value in the bottom-right cell, since it represents the minimum path sum to the destination.

The brute-force approach is slow because it repeatedly recomputes the best cost from the same cell. Dynamic programming addresses this issue by storing, for each cell, the minimum path sum required to reach it, ensuring that every cell is solved only once.

Here is a visual representation of the algorithm discussed above:

1 / 10

Python Implementation

Let’s implement the algorithm as discussed above:

def minPathSum(grid):
    # Compute grid dimensions (rows = m, columns = n)
    m = len(grid)
    n = len(grid[0])
    
    # Traverse the grid left-to-right, top-to-bottom
    for i in range(m):
        for j in range(n):
            # Top row cells can only be reached from the left neighbor
            if i == 0 and j > 0:
                grid[i][j] += grid[i][j - 1]
            # Leftmost column cells can only be reached from the cell above
            elif j == 0 and i > 0:
                grid[i][j] += grid[i - 1][j]
            elif i > 0 and j > 0:
                # For interior cells, add the cheaper of:
                # - coming from above (i-1, j)
                # - coming from the left (i, j-1)
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    
    # The destination cell holds the minimum total path cost
    return grid[m - 1][n - 1]



# driver code
def main():
    grids = [
        [[1, 3], [2, 4]],
        [[0, 2, 5], [1, 1, 1], [4, 2, 0]],
        [[7]],
        [[9, 1, 2, 3], [4, 8, 1, 1], [2, 0, 3, 4]],
        [[1, 0, 2], [3, 4, 0], [1, 2, 1], [2, 1, 0]],
    ]

    for i in range(len(grids)):
        grid_copy = [row[:] for row in grids[i]]
        print(i + 1, ".\tGrid: ", grids[i], sep="")
        print("\tMinimum path sum:", minPathSum(grid_copy))
        print("-" * 75)

if __name__ == "__main__":
    main()

Time Complexity

The time complexity of the solution is $O(m⋅n)$ because each cell in the grid is updated exactly once.

Space Complexity

The space complexity of the solution is $O(1)$ because the input grid is reused to store the running minimum sums, and no auxiliary space is used.