Problem Description

You are given a m x n grid filled with non-negative numbers. Your task is to find a path from the top-left corner of the grid to the bottom-right corner that minimizes the sum of all numbers along the path.

The movement constraints are:

• You can only move either down or right at any point in time
• You cannot move up or left
• You cannot move diagonally

For example, if you have a grid like:

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

Starting from position (0,0) with value 1, you need to reach position (2,2) with value 1. One possible path could be: 1 → 3 → 1 → 1 → 1 (going right, right, down, down), which gives a sum of 7. Another path could be: 1 → 1 → 4 → 2 → 1 (going down, down, right, right), which gives a sum of 9. The optimal path would be: 1 → 3 → 1 → 1 → 1 with the minimum sum of 7.

The goal is to determine this minimum possible sum for any given grid.

Intuition

The key insight is that to reach any cell (i, j) in the grid, we can only come from two possible directions: either from the cell directly above it (i-1, j) or from the cell directly to its left (i, j-1). This is because we can only move down or right.

This observation leads us to think about the problem in terms of subproblems. If we know the minimum path sum to reach (i-1, j) and the minimum path sum to reach (i, j-1), then the minimum path sum to reach (i, j) would be:

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

We take the minimum of the two possible paths and add the current cell's value.

This naturally suggests a dynamic programming approach where we build up the solution progressively. Starting from the top-left corner, we can calculate the minimum path sum for each cell by using the already computed minimum path sums of the cells we could have come from.

For the first row and first column, there's only one way to reach each cell:

• For cells in the first row, we can only come from the left
• For cells in the first column, we can only come from above

By systematically computing the minimum path sum for each cell from top-left to bottom-right, we eventually find the minimum path sum to reach the bottom-right corner, which is our answer.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using dynamic programming with a 2D array f where f[i][j] represents the minimum path sum from the top-left corner (0, 0) to position (i, j).

Step 1: Initialize the DP array

• Create a 2D array f with the same dimensions as the grid (m x n)
• Set f[0][0] = grid[0][0] as the starting point

Step 2: Fill the first column

• For each cell in the first column (where j = 0), we can only arrive from the cell above
• Therefore: f[i][0] = f[i-1][0] + grid[i][0] for all i from 1 to m-1
• This represents the cumulative sum going straight down

Step 3: Fill the first row

• For each cell in the first row (where i = 0), we can only arrive from the cell to the left
• Therefore: f[0][j] = f[0][j-1] + grid[0][j] for all j from 1 to n-1
• This represents the cumulative sum going straight right

Step 4: Fill the rest of the grid

• For any other cell (i, j) where both i > 0 and j > 0, we can arrive from either:
  • The cell above: f[i-1][j]
  • The cell to the left: f[i][j-1]
• We choose the path with the minimum sum: f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]

Step 5: Return the result

• The minimum path sum to reach the bottom-right corner is stored in f[m-1][n-1]
• We can access this using f[-1][-1] in Python

The time complexity is O(m × n) as we visit each cell once, and the space complexity is also O(m × n) for the DP array.

Example Walkthrough

Let me walk through a small example to illustrate the solution approach using this grid:

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

Step 1: Initialize the DP array

Create a 3×3 DP array f and set the starting point:

f[0][0] = grid[0][0] = 1

f = [1, ?, ?]
    [?, ?, ?]
    [?, ?, ?]

Step 2: Fill the first column

For cells in the first column, we can only come from above:

• f[1][0] = f[0][0] + grid[1][0] = 1 + 1 = 2
• f[2][0] = f[1][0] + grid[2][0] = 2 + 4 = 6

f = [1, ?, ?]
    [2, ?, ?]
    [6, ?, ?]

Step 3: Fill the first row

For cells in the first row, we can only come from the left:

• f[0][1] = f[0][0] + grid[0][1] = 1 + 3 = 4
• f[0][2] = f[0][1] + grid[0][2] = 4 + 1 = 5

f = [1, 4, 5]
    [2, ?, ?]
    [6, ?, ?]

Step 4: Fill the remaining cells

For each remaining cell, choose the minimum path from above or left:

Position (1,1):

• From above: f[0][1] = 4
• From left: f[1][0] = 2
• f[1][1] = min(4, 2) + grid[1][1] = 2 + 5 = 7

Position (1,2):

• From above: f[0][2] = 5
• From left: f[1][1] = 7
• f[1][2] = min(5, 7) + grid[1][2] = 5 + 1 = 6

Position (2,1):

• From above: f[1][1] = 7
• From left: f[2][0] = 6
• f[2][1] = min(7, 6) + grid[2][1] = 6 + 2 = 8

Position (2,2):

• From above: f[1][2] = 6
• From left: f[2][1] = 8
• f[2][2] = min(6, 8) + grid[2][2] = 6 + 1 = 7

Final DP array:

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

Step 5: Return the result

The minimum path sum is f[2][2] = 7, which corresponds to the path: 1 → 3 → 1 → 1 → 1 (right, right, down, down).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the grid. This is because:

• Initializing the first cell f[0][0] takes O(1) time
• Filling the first column requires iterating through m-1 cells, taking O(m) time
• Filling the first row requires iterating through n-1 cells, taking O(n) time
• The nested loops iterate through (m-1) × (n-1) cells, with each cell computation taking O(1) time
• Overall: O(1) + O(m) + O(n) + O(m × n) = O(m × n)

The space complexity is O(m × n) because the algorithm creates a 2D array f with dimensions m × n to store the minimum path sum for each cell. Each cell in this array stores a single integer value, resulting in total space usage proportional to the grid size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Grid Instead of Using Separate DP Array

A common mistake is trying to save space by modifying the input grid directly to store the DP values. This can lead to issues if the original grid needs to be preserved or if the function is called multiple times with the same grid reference.

Problematic Code:

def minPathSum(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
  
    # Modifying grid directly - BAD PRACTICE
    for row in range(1, rows):
        grid[row][0] += grid[row - 1][0]
  
    for col in range(1, cols):
        grid[0][col] += grid[0][col - 1]
  
    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[-1][-1]

Solution: Always create a separate DP array unless explicitly stated that modifying the input is acceptable.

2. Incorrect Initialization of Boundaries

Another frequent error is forgetting to properly initialize the first row and column, or starting the loop indices incorrectly.

Problematic Code:

def minPathSum(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
  
    # WRONG: Starting from index 0 instead of 1
    for row in range(0, rows):  # Should be range(1, rows)
        dp[row][0] = dp[row - 1][0] + grid[row][0]  # This will cause IndexError
  
    # Or forgetting to initialize boundaries at all
    for row in range(1, rows):
        for col in range(1, cols):
            dp[row][col] = min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col]
    # This leaves first row and column (except [0][0]) as zeros

Solution: Carefully initialize boundaries before filling the interior cells, and ensure loop indices start from 1 for boundary initialization.

3. Space Optimization Pitfall When Using 1D Array

When optimizing space to O(n) using a 1D array, a common mistake is not properly updating values or using the wrong previous values.

Problematic Code:

def minPathSum(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [0] * cols
  
    for row in range(rows):
        for col in range(cols):
            if row == 0 and col == 0:
                dp[col] = grid[0][0]
            elif row == 0:
                dp[col] = dp[col - 1] + grid[row][col]
            elif col == 0:
                dp[col] = dp[col] + grid[row][col]  # dp[col] holds value from previous row
            else:
                # WRONG: Not handling the update correctly
                dp[col] = min(dp[col], dp[col - 1]) + grid[row][col]

Correct Space-Optimized Solution:

def minPathSum(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [float('inf')] * cols
    dp[0] = 0
  
    for row in range(rows):
        for col in range(cols):
            if col == 0:
                dp[col] = dp[col] + grid[row][col]
            else:
                dp[col] = min(dp[col], dp[col - 1]) + grid[row][col]
  
    return dp[-1]