LeetCode 64 - Minimum Path Sum

The problem gives us a two dimensional grid of size m x n, where each cell contains a non-negative integer. We begin at the top-left corner of the grid, specifically at position (0, 0), and want to reach the bottom-right corner at position (m - 1, n - 1).

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 64

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid of size m x n, where each cell contains a non-negative integer. We begin at the top-left corner of the grid, specifically at position (0, 0), and want to reach the bottom-right corner at position (m - 1, n - 1).

The objective is to find a path whose total sum of values is as small as possible. The cost of a path is the sum of every number encountered along the route, including both the starting cell and the ending cell.

There is an important movement restriction: from any cell, we are only allowed to move either right or down. Moving left, up, or diagonally is not allowed. This restriction significantly shapes the problem because it means every path has a predictable structure.

For example, in the grid:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

one valid path could be:

1 → 3 → 1 → 1 → 1

which produces a total sum of 7, and this happens to be the minimum possible.

The input consists of:

  • grid, a two dimensional matrix of non-negative integers
  • m, the number of rows
  • n, the number of columns

The output is a single integer representing the minimum path sum from the top-left to the bottom-right corner.

The constraints provide useful clues about the expected solution:

  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

A 200 x 200 grid contains up to 40,000 cells. Since every cell may need to be processed, an O(m × n) solution is very reasonable. However, exponential approaches that explore every possible path would become infeasible.

A naive implementation could struggle with several edge cases. A single-cell grid such as [[5]] is important because the answer is simply the value of that one cell. A single row or single column grid is also noteworthy because there is only one possible path. Another consideration is that all values are non-negative, which guarantees that dynamic programming works naturally because adding more steps cannot unexpectedly reduce previously computed costs.

The problem guarantees that the grid is valid, non-empty, and rectangular, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to explore every possible path from the top-left corner to the bottom-right corner using recursion or depth-first search.

At each cell, we have at most two choices:

  1. Move right
  2. Move down

We recursively compute the minimum path sum for both possibilities and choose the smaller result.

For example:

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

This approach is correct because it explicitly evaluates every valid route and selects the minimum total sum.

However, it is far too slow. Many subproblems are recomputed repeatedly. For instance, the minimum path from a particular cell to the destination may be recalculated dozens or thousands of times from different recursive branches.

Since each step branches into up to two recursive calls, the total number of possibilities grows exponentially, approximately O(2^(m+n)), making it impractical for grids as large as 200 x 200.

Key Insight for an Optimal Solution

The important observation is that the minimum cost to reach a cell depends only on the minimum cost of its neighboring cells.

To reach cell (i, j), we can only come from:

  • The cell above (i - 1, j)
  • The cell to the left (i, j - 1)

Therefore:

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

This is a classic dynamic programming problem because:

  1. There are overlapping subproblems
  2. The optimal answer can be built from smaller optimal answers

Instead of recomputing values repeatedly, we store the minimum path sum for each cell and reuse it.

We can even modify the input grid in place to save memory, treating each cell as storing the minimum cost to reach that position.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Recursively explores all possible paths
Optimal Dynamic Programming O(m × n) O(1) extra space Reuses previously computed results by updating the grid

Algorithm Walkthrough

  1. Start at the top-left cell. Since this is the starting position, its value remains unchanged because there is no previous path cost to add.
  2. Process the first row. Since movement is restricted to the right or down, every cell in the first row can only be reached from the left. Therefore, accumulate the running path sum from left to right.
  3. Process the first column. Similarly, every cell in the first column can only be reached from above. Accumulate the running path sum from top to bottom.
  4. Process the remaining cells row by row. For each cell (i, j), determine the smaller path sum between:
  • The cell directly above (i - 1, j)
  • The cell directly to the left (i, j - 1)
  1. Add the smaller of those two values to the current cell value. This transforms the cell into the minimum cost required to reach that position.
  2. Continue until the bottom-right corner is processed.
  3. Return the value in the bottom-right cell, since it now contains the minimum path sum from start to finish.

Why it works

The algorithm works because of the optimal substructure property. Any minimum path to a cell must itself come from a minimum path to either the cell above or the cell to the left. If we already know the minimum path sums for those neighboring cells, choosing the smaller one guarantees that the current cell also gets the minimum possible cost. By filling the grid systematically from top-left to bottom-right, every required subproblem has already been solved before it is needed.

Python Solution

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        # Process first row
        for col in range(1, cols):
            grid[0][col] += grid[0][col - 1]

        # Process first column
        for row in range(1, rows):
            grid[row][0] += grid[row - 1][0]

        # Process remaining cells
        for row in range(1, rows):
            for col in range(1, cols):
                grid[row][col] += min(
                    grid[row - 1][col],
                    grid[row][col - 1]
                )

        return grid[rows - 1][cols - 1]

The implementation begins by determining the number of rows and columns in the grid.

The first row is processed separately because every position can only be reached from the left. We accumulate the running sum so that each cell stores the minimum cost to reach it.

The first column is handled similarly. Since movement can only be downward in this column, each cell adds the value from the cell directly above.

After the boundaries are initialized, we process the rest of the grid. At each position, we look at the minimum path sum from the top and left neighbors. Since those values already represent the best way to reach those cells, taking the smaller one guarantees the optimal result for the current cell.

The algorithm updates the original grid in place, avoiding the need for an additional dynamic programming table. Finally, the bottom-right cell contains the answer.

Go Solution

func minPathSum(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	// Process first row
	for col := 1; col < cols; col++ {
		grid[0][col] += grid[0][col-1]
	}

	// Process first column
	for row := 1; row < rows; row++ {
		grid[row][0] += grid[row-1][0]
	}

	// Process remaining cells
	for row := 1; row < rows; row++ {
		for col := 1; col < cols; col++ {
			if grid[row-1][col] < grid[row][col-1] {
				grid[row][col] += grid[row-1][col]
			} else {
				grid[row][col] += grid[row][col-1]
			}
		}
	}

	return grid[rows-1][cols-1]
}

The Go implementation follows exactly the same dynamic programming logic as the Python version.

One small difference is that Go does not provide a built-in min() function for integers, so we explicitly compare the top and left values using an if statement.

The solution modifies the input slice in place, just like the Python version. Since the problem guarantees valid input dimensions, there is no need for additional checks for empty grids.

Go integers are also safe here because the maximum path sum is bounded. At worst, a 200 x 200 grid with values of 200 produces a sum far below the limits of Go's int type.

Worked Examples

Example 1

Input

grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Initial grid:

Row Values
0 [1, 3, 1]
1 [1, 5, 1]
2 [4, 2, 1]

Step 1: Process first row

Operation Grid State
3 += 1 [[1,4,1],[1,5,1],[4,2,1]]
1 += 4 [[1,4,5],[1,5,1],[4,2,1]]

Step 2: Process first column

Operation Grid State
1 += 1 [[1,4,5],[2,5,1],[4,2,1]]
4 += 2 [[1,4,5],[2,5,1],[6,2,1]]

Step 3: Process inner cells

Cell (1,1):

5 + min(4, 2) = 7

Grid:

[
  [1,4,5],
  [2,7,1],
  [6,2,1]
]

Cell (1,2):

1 + min(5, 7) = 6

Grid:

[
  [1,4,5],
  [2,7,6],
  [6,2,1]
]

Cell (2,1):

2 + min(7, 6) = 8

Grid:

[
  [1,4,5],
  [2,7,6],
  [6,8,1]
]

Cell (2,2):

1 + min(6, 8) = 7

Final grid:

[
  [1,4,5],
  [2,7,6],
  [6,8,7]
]

Final answer:

7

Example 2

Input

grid = [
  [1,2,3],
  [4,5,6]
]

Initial grid:

Row Values
0 [1, 2, 3]
1 [4, 5, 6]

Step 1: Process first row

[
  [1,3,6],
  [4,5,6]
]

Step 2: Process first column

[
  [1,3,6],
  [5,5,6]
]

Step 3: Process remaining cells

Cell (1,1):

5 + min(3,5) = 8

Cell (1,2):

6 + min(6,8) = 12

Final grid:

[
  [1,3,6],
  [5,8,12]
]

Final answer:

12

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every cell is visited exactly once
Space O(1) The grid is modified in place, requiring no extra DP array

The algorithm processes every cell exactly one time, making the runtime proportional to the number of cells in the grid. Since the grid contains m × n cells, the time complexity is O(m × n).

The space complexity is O(1) extra space because the dynamic programming results are stored directly inside the input grid. No additional matrix is allocated.

Test Cases

solution = Solution()

# Example 1
assert solution.minPathSum([
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]) == 7  # standard example

# Example 2
assert solution.minPathSum([
    [1, 2, 3],
    [4, 5, 6]
]) == 12  # rectangular grid

# Single cell
assert solution.minPathSum([
    [5]
]) == 5  # smallest possible input

# Single row
assert solution.minPathSum([
    [1, 2, 3, 4]
]) == 10  # only move right

# Single column
assert solution.minPathSum([
    [1],
    [2],
    [3]
]) == 6  # only move down

# All zeros
assert solution.minPathSum([
    [0, 0],
    [0, 0]
]) == 0  # minimum possible values

# Prefer non-straight path
assert solution.minPathSum([
    [1, 100, 1],
    [1, 1, 1]
]) == 4  # avoids expensive path

# Larger square grid
assert solution.minPathSum([
    [1, 2, 5],
    [3, 2, 1]
]) == 6  # optimal turn path

# Large values
assert solution.minPathSum([
    [200, 200],
    [200, 200]
]) == 600  # tests upper cell values
Test Why
[[1,3,1],[1,5,1],[4,2,1]] Verifies the standard example
[[1,2,3],[4,5,6]] Tests a rectangular grid
[[5]] Validates single-cell handling
[[1,2,3,4]] Tests single-row movement
[[1],[2],[3]] Tests single-column movement
[[0,0],[0,0]] Ensures zero values are handled correctly
[[1,100,1],[1,1,1]] Confirms algorithm chooses cheaper turns
[[1,2,5],[3,2,1]] Tests non-obvious optimal route
[[200,200],[200,200]] Verifies handling of maximum cell values

Edge Cases

Single Cell Grid

A grid such as [[5]] is the smallest valid input. Since the start and destination are the same cell, the minimum path sum is simply the value already present. A buggy implementation might accidentally skip processing or attempt invalid indexing. This implementation handles it naturally because all loops start at index 1, meaning no extra work occurs and the single value is returned.

Single Row or Single Column

If the grid contains only one row or one column, there is exactly one possible path. In a single row, we can only move right. In a single column, we can only move down. These cases often break implementations that assume both upward and leftward neighbors exist. Here, the first row and first column are initialized separately, ensuring correct handling.

Grids With Large Numbers

Although each cell value can be as high as 200, the total path sum can become large across many cells. Some implementations may worry about overflow or performance degradation. However, the maximum possible path length is limited, and the resulting sum remains safely within integer limits in both Python and Go.

Paths That Require Turning

The optimal path is not always visually obvious or straight. For example:

[
  [1,100,1],
  [1,1,1]
]

A greedy strategy that always chooses the smallest immediate neighbor could make poor choices in more complex cases. Dynamic programming avoids this issue by computing the globally optimal path sum for every cell, ensuring the final answer is always correct.