Minimum Path Sum

This question is asked by Google. Given an N×M matrix, grid, where each cell in the matrix represents the cost of stepping on the current cell, return the minimum cost to traverse from the top-left hand corner of the matrix to the bottom-right hand corner.

Note: You may only move down or right while traversing the grid.

Example(s)

Example 1:

Input: grid = [
    [1, 1, 3],
    [2, 3, 1],
    [4, 6, 1]
]

Output: 7
Explanation:
The path that minimizes cost is: 1 → 1 → 3 → 1 → 1
Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
Sum: 1 + 1 + 3 + 1 + 1 = 7

Example 2:

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

Output: 7
Explanation:
Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
Sum: 1 + 3 + 1 + 1 + 1 = 7

Example 3:

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

Output: 12
Explanation:
Path: (0,0) → (0,1) → (0,2) → (1,2)
Sum: 1 + 2 + 3 + 6 = 12

Solution

The solution uses Dynamic Programming:

1. Base case: Top-left corner is the starting point
2. First row: Can only come from left
3. First column: Can only come from top
4. Other cells: Minimum of top or left + current cell cost

JavaScript Solution

JavaScript Solution - Dynamic Programming

/**
* Find minimum path sum from top-left to bottom-right
* @param {number[][]} grid - 2D matrix of costs
* @return {number} - Minimum path sum
*/
function minPathSum(grid) {
if (!grid || grid.length === 0 || grid[0].length === 0) {
  return 0;
}

const rows = grid.length;
const cols = grid[0].length;

// Create DP table
const dp = Array(rows).fill().map(() => Array(cols).fill(0));

// Base case: top-left corner
dp[0][0] = grid[0][0];

// Fill first row: can only come from left
for (let j = 1; j < cols; j++) {
  dp[0][j] = dp[0][j - 1] + grid[0][j];
}

// Fill first column: can only come from top
for (let i = 1; i < rows; i++) {
  dp[i][0] = dp[i - 1][0] + grid[i][0];
}

// Fill rest of the table
for (let i = 1; i < rows; i++) {
  for (let j = 1; j < cols; j++) {
    // Minimum of coming from top or left
    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
  }
}

return dp[rows - 1][cols - 1];
}

// Test cases
const grid1 = [
[1, 1, 3],
[2, 3, 1],
[4, 6, 1]
];
console.log('Example 1:', minPathSum(grid1)); 
// 7

const grid2 = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
];
console.log('Example 2:', minPathSum(grid2)); 
// 7

const grid3 = [
[1, 2, 3],
[4, 5, 6]
];
console.log('Example 3:', minPathSum(grid3)); 
// 12

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Dynamic Programming

from typing import List

def min_path_sum(grid: List[List[int]]) -> int:
  """
  Find minimum path sum from top-left to bottom-right
  
  Args:
      grid: 2D matrix of costs
      
  Returns:
      int: Minimum path sum
  """
  if not grid or not grid[0]:
      return 0
  
  rows = len(grid)
  cols = len(grid[0])
  
  # Create DP table
  dp = [[0] * cols for _ in range(rows)]
  
  # Base case: top-left corner
  dp[0][0] = grid[0][0]
  
  # Fill first row: can only come from left
  for j in range(1, cols):
      dp[0][j] = dp[0][j - 1] + grid[0][j]
  
  # Fill first column: can only come from top
  for i in range(1, rows):
      dp[i][0] = dp[i - 1][0] + grid[i][0]
  
  # Fill rest of the table
  for i in range(1, rows):
      for j in range(1, cols):
          # Minimum of coming from top or left
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
  
  return dp[rows - 1][cols - 1]

# Test cases
grid1 = [
  [1, 1, 3],
  [2, 3, 1],
  [4, 6, 1]
]
print('Example 1:', min_path_sum(grid1))  
# 7

grid2 = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
print('Example 2:', min_path_sum(grid2))  
# 7

grid3 = [
  [1, 2, 3],
  [4, 5, 6]
]
print('Example 3:', min_path_sum(grid3))  
# 12

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Space-Optimized)

Here's a space-optimized version using only one row:

JavaScript Optimized

/**
 * Space-optimized: O(min(m, n)) space
 */
function minPathSumOptimized(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }
  
  const rows = grid.length;
  const cols = grid[0].length;
  
  // Use only one row for DP
  const dp = Array(cols).fill(0);
  dp[0] = grid[0][0];
  
  // Fill first row
  for (let j = 1; j < cols; j++) {
    dp[j] = dp[j - 1] + grid[0][j];
  }
  
  // Process remaining rows
  for (let i = 1; i < rows; i++) {
    dp[0] += grid[i][0]; // First column
    for (let j = 1; j < cols; j++) {
      dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
    }
  }
  
  return dp[cols - 1];
}

Python Optimized

def min_path_sum_optimized(grid: List[List[int]]) -> int:
    """
    Space-optimized: O(min(m, n)) space
    """
    if not grid or not grid[0]:
        return 0
    
    rows = len(grid)
    cols = len(grid[0])
    
    # Use only one row for DP
    dp = [0] * cols
    dp[0] = grid[0][0]
    
    # Fill first row
    for j in range(1, cols):
        dp[j] = dp[j - 1] + grid[0][j]
    
    # Process remaining rows
    for i in range(1, rows):
        dp[0] += grid[i][0]  # First column
        for j in range(1, cols):
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
    
    return dp[cols - 1]

Complexity

• Time Complexity: O(m × n) - Where m and n are the dimensions of the grid. We visit each cell once.
• Space Complexity:
  • Standard DP: O(m × n) - For the DP table
  • Optimized: O(min(m, n)) - Using only one row/column

Approach

The solution uses Dynamic Programming:

1. DP table:

   • dp[i][j] represents the minimum cost to reach cell (i, j)

2. Base case:

   • dp[0][0] = grid[0][0] (starting point)

3. First row:

   • Can only come from left: dp[0][j] = dp[0][j-1] + grid[0][j]

4. First column:

   • Can only come from top: dp[i][0] = dp[i-1][0] + grid[i][0]

5. Other cells:

   • Can come from top or left: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

6. Result:

   • Return dp[rows-1][cols-1] (bottom-right corner)

Key Insights

• Dynamic Programming: Optimal substructure - optimal path to (i,j) uses optimal paths to (i-1,j) or (i,j-1)
• Only two directions: Can only move down or right
• Base cases: First row and first column have only one way to reach
• Bottom-up: Fill table from top-left to bottom-right
• O(m×n) time: Must process all cells

Step-by-Step Example

Let's trace through Example 1: grid = [[1,1,3],[2,3,1],[4,6,1]]

Grid:
  [1, 1, 3]
  [2, 3, 1]
  [4, 6, 1]

DP table initialization:
  dp[0][0] = grid[0][0] = 1

Fill first row:
  dp[0][1] = dp[0][0] + grid[0][1] = 1 + 1 = 2
  dp[0][2] = dp[0][1] + grid[0][2] = 2 + 3 = 5

Fill first column:
  dp[1][0] = dp[0][0] + grid[1][0] = 1 + 2 = 3
  dp[2][0] = dp[1][0] + grid[2][0] = 3 + 4 = 7

Fill rest:
  dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1]
           = min(2, 3) + 3 = 2 + 3 = 5
  
  dp[1][2] = min(dp[0][2], dp[1][1]) + grid[1][2]
           = min(5, 5) + 1 = 5 + 1 = 6
  
  dp[2][1] = min(dp[1][1], dp[2][0]) + grid[2][1]
           = min(5, 7) + 6 = 5 + 6 = 11
  
  dp[2][2] = min(dp[1][2], dp[2][1]) + grid[2][2]
           = min(6, 11) + 1 = 6 + 1 = 7

DP table:
  [1, 2, 5]
  [3, 5, 6]
  [7, 11, 7]

Result: dp[2][2] = 7

Visual Representation

Example 1: grid = [[1,1,3],[2,3,1],[4,6,1]]

Grid:
    0  1  2
0 [ 1  1  3 ]
1 [ 2  3  1 ]
2 [ 4  6  1 ]

DP table (minimum cost to reach each cell):
    0  1  2
0 [ 1  2  5 ]
1 [ 3  5  6 ]
2 [ 7 11  7 ]

Optimal path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
Cost: 1 + 1 + 3 + 1 + 1 = 7

Edge Cases

• 1×1 grid: Return grid[0][0]
• 1×n grid: Sum of first row
• n×1 grid: Sum of first column
• All same values: Any path has same cost
• Large values: May need to handle overflow

Important Notes

• Only down or right: Cannot move up or left
• Dynamic Programming: Optimal substructure property
• Bottom-up approach: Fill table from top-left to bottom-right
• Space optimization: Can reduce to O(min(m,n)) space
• O(m×n) time: Must process all cells

Why Dynamic Programming Works

Optimal Substructure:

• To reach (i,j) with minimum cost, we must come from either (i-1,j) or (i,j-1)
• If we use the minimum cost path to (i-1,j) or (i,j-1), we get minimum cost to (i,j)
• This allows us to build solution bottom-up

Overlapping Subproblems:

• Multiple paths may pass through the same cell
• We compute minimum cost to each cell once and reuse it

Related Problems

• Unique Paths: Count paths (similar structure)
• Unique Paths II: With obstacles
• Triangle: Different DP problem
• Dungeon Game: Different grid DP problem

Takeaways

• Dynamic Programming solves this efficiently
• Optimal substructure allows bottom-up approach
• Two directions only simplifies the problem
• O(m×n) time is optimal (must process all cells)
• Space can be optimized to O(min(m,n))